int binary_search(int* a, int len, int goal){
int low = 0;
int high = len -1;
while (low <= high) {
int middle = (high - low) / 2 + low; // 直接使用(high + low) / 2 可能导致溢出
if (a[middle] == goal)
return middle;
//在左半边
if (a[middle] > goal)
high = middle - 1;
//在右半边
else
low = middle + 1;
}
//没找到
return -1;
}
原理并不复杂，[low,high]构成了潜在区间，如果中值不等于目标，则减半对应的区间。
有一个问题：为什么循环条件是小于等于，而不是小于？
因为假设在[1,3]中寻找2，low和high会重合，但是还不确定能否找到目标值，循环不应该停止。
最后的情形
因为整数求一般是向下取整，所以最后剩下两三个数的时候，会有一些情况：
最后剩下两三个数的情况
最后剩下两个数
最后剩下三个数
思考
对于二分搜索来说，如果找不到，每次都会移动左边界或右边界，每次边界至少会移动1个位置，且两个边界每次只有一个移动，而且移动时不会超过另一侧的边界，那么两边界最终一定会相遇。每次移动时，目标都处于两边界之间(含)，所以最后两边界重合时，目标只可能是两边界重合的位置或不存在。所以即使两边界重合，还要做一次判断才可以。所以循环条件加入了等于的情况，其实如果不加等于，后续做一次判断，也是完全可以的。
有重复值的二分查找
对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。
给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。
int findPos(vector<int> arr, int n, int num) {
if(n==0)
return -1;
int left=0,right=n-1;
while(left<right){
int mid=left+(right-left)/2;
if(arr[mid]<num){
left=mid+1;
}else if(arr[mid]>num){
right=mid-1;
}else{
right=mid;
}
}
if(arr[left]==num)
return left;
else
return -1;
}
两者最大的区别在于，如果mid指示的值等于目标值，那么还不能确定目标值的最左位置，但mid位置依然在我们的左右边界内。此时右边界赋值为mid，而不是mid-1。因为不能排除mid出待定区间。
这样也会有问题，那就是每次循环不保证一定会缩减边界区间，会出现死循环。死循环发生在mid==right的情况，即left==right的时候。所以循环条件不能包括等于，而且需要在循环结束后再做一次判断。
思考
对于二分查找来说，我们界定一个区间，这个区间表示了目标潜在的可能位置。每次迭代时缩减此区间，则最终当此区间只有一个位置时，目标要么不存在，要么一定在该位置。
局部最小值
arr中数据呈波谷状排列，已知arr中任意两个相邻的数都不相等，写一个函数返回arr中波谷位置。
思路：对于中间值mid，需要判断mid和左右邻居的大小关系。如果是波谷，那么其左右邻居一定都大于mid。同理，可以判断是否是递减区或递增区，再做进一步调整。
注意：如果波谷点在首尾的位置的话，立即返回首尾位置。
int getLessIndex(vector<int> arr) {
int len = arr.size();
if (len == 0) return -1;
if (len == 1) return 0;
if (arr[0] < arr[1]) return 0;
if (arr[len-1] < arr[len-2]) return len-1;
int left=0,right=len-1;
while (left <= right) {
int mid = left+(right-left)/2;
if (arr[mid+1] > arr[mid] && arr[mid-1] > arr[mid]) {
return mid;
}else if (arr[mid] > arr[mid-1]) {
right = mid;
}else if (arr[mid] > arr[mid+1]) {
left = mid;
}
}
return -1;
}
循环有序数组
对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。
int getMin(vector<int> arr, int n) {
if(n<=1)
return arr[0];
int left=0,right=n-1;
while(left<right){
if(arr[left]<arr[right])
return arr[left];
int mid=left+(right-left)/2;
if(arr[mid]>arr[left]){
left=mid+1;
}else if(arr[mid]<arr[left]){
right=mid;
}else{
if(arr[left]>arr[right])
left=mid+1;
else{
int i;
for(i=left;i<mid;++i){
if(arr[i]!=arr[left])
break;
}
if(i==mid)
left=mid+1;
else
right=mid-1;
}
}
}
return arr[left];
}
说明：
假设本来的序列是[arr1,arr2],移动后是[arr2,arr1].以为原始序列单调不减，所以arr1中元素小于等于arr2中元素。left是arr2的首，right是arr1的尾，所以arr[left]应该大于等于arr[right]。否则该串并未发生交换，或者left已经找到了最小值点，应立即返回left。
对于[1,2,3,3,4]，交换后[3,4,1,2,3];对于交换后的序列，如果mid值大于等于left值，则应处于arr1队列；如果小于，则一定处于arr2队列。但这其中有一个问题，如果left和right和mid值都相等，那么就无法判断了。比如[1 2 2 2 2 2]->[2 1 2 2 2 2]->[2 2 2 2 1 2]首尾以及mid都是2，但是1可能在arr1和arr2是不确定的。这种情况arr1和arr2中一定有一个全部元素相等的序列，只需对其中一个序列进行遍历来判断即可。
所以策略如下：
- 如果left值小于right，则返回left。此时表示最小值已找到。
- 如果mid值大于left，则mid应处于arr2序列。缩减左边界至mid后一位
- 如果mid值大于right，则mid应处于arr1序列。缩减右边界至mid前一位
- 如果mid值等于left，判断left和right值是否相等。
- 若否，则mid应处于arr2序列，缩减左边界至mid后一位
- 若是，则需遍历[left,mid],判断其是否是全等序列，再调整区间边界。
关于终止条件
如果[4 1 2]的情况，判定mid属于arr1序列，会缩减左边界，此时是[1 2],这时候会触发终止条件。所以在决定终止条件的时候，需要想清楚最终可能的情况。
