二分法

本文仅为作者自学之用，系统为macOS，不保证信息准确。
用题型来分的话，二分法可以简单分为两种：

1. 对于一个没有重复的有序数列，需要用二分法找到某一个数的准确位置；

int start = 0;
int end = nums.length;
while(start <= end){
  mid = start + (end - start)/2;
  if(nums[mid]==target){
    return mid;
  }
  if(nums[mid] > target){
    end = mid - 1;
  }
  if(nums[mid] < target){
    start = mid + 1;
  }
}
return start;

这个时候的start的位置满足以下条件：

• 假如存在target，那么start就是target的位置
• 假如不存在target，那么start的位置就是第一个大于target的数的位置；
• 假如不存在target，而且数组末尾数也比target小，那么start就是数组的长度（也就是数组末尾数的角标数+1）

为什么start是这个结果呢？需要自己穷举各种不同的输入来看，发现输出都满足同一种结论

2.对于一个有重复的有序数列，用二分法寻找第一个大于等于target的数的位置；

int start = 0;
int end = nums.length;
while(start < end){
  mid = start + (end - start)/2;
  if(nums[mid] < target){
    start = mid + 1;
  }
  else{
    end = mid;
  }
}
return start;

这个程序返回的是第一个大于等于target的数的位置。

• 如果最小的数都比target大，则start为0
• 如果最大的数都比target小，则start = end = 数组长度
• 如果数组中存在target，则指向第一个target（重复的话）