本文仅为作者自学之用，系统为macOS，不保证信息准确。
用题型来分的话，二分法可以简单分为两种：
- 对于一个没有重复的有序数列，需要用二分法找到某一个数的准确位置；
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（重复的话）
