https://hackernoon.com/binary-search-in-detail-914944a1434a
Given an integer x, find the maximum element y in an array of size N that satisfies the condition y <= x
http://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html
loop invariant 循环不变式
http://814193594.blog.51cto.com/10729329/1726286
java.util.Arrays.binarySearch0(long[], int, int, long)
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
lower_bound upper_bound binary_search的最佳写法
https://www.zybuluo.com/rapiz/note/339250
http://blog.csdn.net/cannon0102/article/details/40113459
http://blog.csdn.net/u014688145/article/details/69094665
https://www.zhihu.com/question/36132386
http://www.geeksforgeeks.org/find-missing-number-geometric-progression/
Xhttps://www.imooc.com/article/19963
以下这个函数是二分查找nums中[left，right)部分，right值取不到，如果查到的话，返回所在地，如果查不到则返回最后一个小于target值得后一个位置。
//右值点不能取到的情况
int binary_search(vector<int>& nums,int left,int right, int target) {
//坑点（1）right究竟能不能取到的问题，这里是不能取到的情况
int i = left;
int j= right;
while(i<j){
int mid = i+(j-i)/2; //坑点（2）这里尽量这么写，因为如果写成(i+j)/2则有溢出的风险
if(nums[mid]>=target) //坑点（3）这个地方大于还是大于等于要依据情况而定
j = mid; //坑点（4）因为右值点反正不能取到，所以j就可以等于mid
else
i = mid+1; //坑点（5）
}
return i;
}
//右值点能取到的情况
int searchInsert(vector<int>& nums,int left,int right, int target) {
int i = left;
int j= right;
while(i<=j ){
int mid = i+(j-i)/2;
if(nums[mid]>=target)
j = mid-1;
else
i = mid+1;
}
return i;
}
一般来说写的二分查找的标准程序应该是右边right值取不到的情况，所以while循环中要加一步判断i是否小于等于nums.size();
对于坑点2，如果是右值点可以取到情况下，必须是i<=j否则会出现查找偏差，比如数组中就一个元素[3]，让查找5的位置，理应返回1，但是此时会输出成0，
对于坑点3，主要应用在如果数组中有重复元素，需要判断其具体要返回什么位置。
对于坑点,5，如果i不加1的，比如i = 0，j= 1 的情况，会出现mid = 0然后一直死循环下去
对于坑点4，依据right能不能取到而定，如果right可以取到则，right必须要-1，不减1的话，还是会出现i = j时的死循环。
https://segmentfault.com/a/1190000011283470
Given an integer x, find the maximum element y in an array of size N that satisfies the condition y <= x
We know that x might not be in the array. So the simple binary search for x in the given array won’t work. But for binary search, all we know is x, the key. We need to find the element in the array that’s the closest to x and less than or equal to x (if it exists).
- How to move low and high?
Whenarray[mid] < x, there is a possibility that the current element might be the answer (since y can be less than x).
So, we shouldn’t discard mid while moving low.
Hence, low becomeslow = mid, notlow = mid + 1
High remains the same as it is irrelevant to our problem statement. - How to compute mid?When we use
mid = low + ((high - low) / 2), we are calculating the lower mid. So when the #elements in the array is even, theif(array[mid] > x)becomes false, so control will go to else clause wherelow = mid. This results in an infinite loop. (why? take an example)
Hence, we take the higher mid, i.e.,mid = low + ((high - low + 1) / 2) - What would be the condition in while loop?Since we are storing the maximum element that is less than or equal to x in low, we should stop when low = high and return
array[low]orarray[high]. Hence, the condition in while loop islow < high.
int binarySearchExample1(int[] array, int key){
int length = array.length;
int low = 0;
int high = length - 1;
while(low < high){
int mid = low + ((high - low + 1) / 2);
int current = array[mid];
if(current == key){
return array[mid];
}
else if(current < key){
low = mid;
}
else{
high = mid - 1;
}
}
return array[low];
}
Given an integer x, find the minimum element y in an array of size N that satisfies the condition
y >= xlow = mid + 1for moving lowhigh = midfor moving highmid = low + ((high - low) / 2)for calculating midlow < highfor the condition in while loop
int binarySearchExample2(int[] array, int key){
int length = array.length;
int low = 0;
int high = length - 1;
while(low < high){
int mid = low + ((high - low) / 2);
int current = array[mid];
if(current == key){
return array[mid];
}
else if(current < key){
low = mid + 1;
}
else{
high = mid;
}
}
return array[high];
}
https://juejin.im/entry/5b875108f265da436152fe8fhttp://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html
loop invariant 循环不变式
1.二分查找值为key的下标，如果不存在返回-1。
循环不变式：
如果key存在于原始数组[0,n-1]，那么它一定在[left,right]中。
int binsearch(int * array, int length, int key) { if(!array) return -1; int left = 0, right = length,mid; ／／ right -1? while(left <= right) { mid = left + (right-left)/2; if(array[mid] < key) { left = mid + 1; }else if(array[mid] > key) { right = mid - 1; }else return mid; } return -1; }
2.二分查找返回key(可能有重复)第一次出现的下标x，如果不存在返回-1
循环不变式：
如果key存在于数组，那么key第一次出现的下标x一定在[left,right]中，且有array[left]<=key, array[right]>=key。
int binsearch_first(int * array, int length,int key) { if(!array) return -1; int left = 0, right = length-1,mid; while(left < right) { mid = left + (right-left)/2; if(array[mid] < key) left = mid+1; else right = mid; } if(array[left] == key) return left; return -1; }
3.二分查找返回key(可能有重复)最后一次出现的下标x，如果不存在返回-1（模仿2的第一版）
与上一种不同，这个算法不能简单地根据对称，从上一个算法直接改过来，由于整数除法总是舍弃小数，mid有时会离left更近一些。所以这种算法只是沿着上一个算法思路的改进，看上去并不是很漂亮。
4.二分查找返回key(可能有重复)最后一次出现的下标x，如果不存在返回-1（修改版）
根据3中的讨论，可以发现不能直接照搬的原因是mid=(left+right)/2的舍弃小数，在left+1==right且array[left]=key时，如果不加以人为干预会导致死循环。既然最终需要干预，干脆把需要干预的时机设置为终止条件就行了。
使用while(left<right-1)可以保证每次循环时数组长度都会至少减一，终止时数组长度可能为2(left+1==right)、1(left==mid，上一次循环时right取mid==left)，但是不可能为0。(每一次循环前总有left<=mid<=right，无论令left=mid还是令right=mid，都不会发生left>right)。同3一样，right总是指向数组中候选的最后一个可能为key的下标，此时只需先检查right后检查left是否为key就能确定x的位置。这样就说明了循环不变式的保持和终止，就不再形式化地写下来了。
对于两种情况的合并：array[mid] == key时，mid有可能是x，不能将其排除；array[mid]<key时，如果让left = mid+1，不会违反循环不变式的条件。但是由上面的讨论可知，将left=mid也是可以的，在达到终止条件前能保证数组长度单调减少。因此把两种情况合并成最终形式。
int binsearch_last_v2(int * array, int length, int key) { if(!array) return -1; int left =0, right = length-1,mid; while(left < right -1) { mid = left + (right-left)/2; if(array[mid] <= key) left = mid; else right = mid; } if(array[right] == key) return right; else if(array[left] == key) return left; else return -1; }
//方法一，采用[]闭区间的方式int BinarrySearch(int *arr, int len, int x){ assert(arr); int left = 0; int right = len - 1; //--------------------- int mid = 0; while (left <= right) //---------------------- { mid = left + (right - left) / 2; if (x > arr[mid]) { left = mid + 1; } else if (x < arr[mid]) { right = mid - 1; //----------------- } else { return mid; } } return (-1);}//方法二，采用[ )左闭右开的方式int BinarrySearch(int *arr, int len, int x){ assert(arr); int left = 0; int right = len; //-----------------区别一 int mid = 0; while (left < right) //---------------------区别二 { mid = left + (right - left) / 2; if (x > arr[mid]) { left = mid + 1; } else if (x < arr[mid]) { right = mid; //-------------区别三 } else { return mid; } } return (-1);}
二分查找主要有三点需要注意：
1、边界问题
2、求中点时的溢出问题
3、有重复值时定位第一个
http://qianzui.github.io/blog/2013-03-15-how-to-correctly-write-binarysearch/http://hedengcheng.com/?p=595static int binarySearch(int[] array, int size, int value) {int lo = 0;int hi = size - 1;while (lo <= hi) {final int mid = (lo + hi) >>> 1;final int midVal = array[mid];if (midVal < value) {lo = mid + 1;} else if (midVal > value) {hi = mid - 1;} else {return mid; // value found}}return ~lo; // value not present}
java.util.Arrays.binarySearch0(long[], int, int, long)
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
lower_bound upper_bound binary_search的最佳写法
public int lower_bound(int [] nums, int target){int l = 0, r = nums.length;//检索范围[l,r)while(l<r){int mid = l+(r-l)/2;if(nums[mid] > target) r = mid;else if(nums[mid] < target) l = mid+1;else r = mid;}return l;}public int upper_bound(int [] nums, int target){int l =0, r = nums.length;//检索范围[l,r)while(l<r){int mid = l+(r-l)/2;if(nums[mid] > target) r = mid;else if(nums[mid] <target) l = mid+1;else l = mid+1;}return r;}
https://www.zybuluo.com/rapiz/note/339250
http://blog.csdn.net/cannon0102/article/details/40113459
http://blog.csdn.net/u014688145/article/details/69094665
https://www.zhihu.com/question/36132386
http://www.geeksforgeeks.org/find-missing-number-geometric-progression/
Given an array that represents elements of geometric progression in order. One element is missing in the progression, find the missing number. It may be assumed that one term is always missing and the missing term is not first or last of series.
A Simple Solution is to linearly traverse the array and find the missing number. Time complexity of this solution is O(n).
An efficient solution to solve this problem in O(Log n) time using Binary Search. The idea is to go to the middle element. Check if the ratio of middle and next to middle is equal to common ratio or not, if not then the missing element lies between mid and mid+1. If the middle element is equal to n/2th term in Geometric Series (Let n be the number of elements in input array), then missing element lies in right half. Else element lies in left half.
Note : Drawback withs this solution are : For larger values or for bigger array, it may cause overflow and/or may take more time to computer powers.
int findMissingRec(int arr[], int low, int high, int ratio){ if (low >= high) return INT_MAX; int mid = low + (high - low)/2; // If element next to mid is missing if (arr[mid+1]/arr[mid] != ratio) return (arr[mid] * ratio); // If element previous to mid is missing if ((mid > 0) && (arr[mid]/arr[mid-1]) != ratio) return (arr[mid-1] * ratio); // If missing element is in right half if (arr[mid] == arr[0] * (pow(ratio, mid)) ) return findMissingRec(arr, mid+1, high, ratio); return findMissingRec(arr, low, mid-1, ratio);}// Find ration and calls findMissingRecint findMissing(int arr[], int n){ // Finding ration assuming that the missing term is // not first or last term of series. int ratio = (float) pow(arr[n-1]/arr[0], 1.0/n); return findMissingRec(arr, 0, n-1, ratio);}Xhttps://www.imooc.com/article/19963
- 差1错误。我们的左端点应该是当前可能区间的最小范围，那么右端点是最大范围呢，还是最大范围+1呢。我们取了中间值之后，在缩小区间时，有没有保持左右端点的这个假设的一致性呢？
- 死循环。我们做的是整数运算，整除2了之后，对于奇数和偶数的行为还不一样，很有可能有些情况下我们并没有减小取值范围，而形成死循环。
- 退出条件。到底什么时候我们才觉得我们找不到呢？
以下这个函数是二分查找nums中[left，right)部分，right值取不到，如果查到的话，返回所在地，如果查不到则返回最后一个小于target值得后一个位置。
//右值点不能取到的情况
int binary_search(vector<int>& nums,int left,int right, int target) {
//坑点（1）right究竟能不能取到的问题，这里是不能取到的情况
int i = left;
int j= right;
while(i<j){
int mid = i+(j-i)/2; //坑点（2）这里尽量这么写，因为如果写成(i+j)/2则有溢出的风险
if(nums[mid]>=target) //坑点（3）这个地方大于还是大于等于要依据情况而定
j = mid; //坑点（4）因为右值点反正不能取到，所以j就可以等于mid
else
i = mid+1; //坑点（5）
}
return i;
}
//右值点能取到的情况
int searchInsert(vector<int>& nums,int left,int right, int target) {
int i = left;
int j= right;
while(i<=j ){
int mid = i+(j-i)/2;
if(nums[mid]>=target)
j = mid-1;
else
i = mid+1;
}
return i;
}
一般来说写的二分查找的标准程序应该是右边right值取不到的情况，所以while循环中要加一步判断i是否小于等于nums.size();
对于坑点2，如果是右值点可以取到情况下，必须是i<=j否则会出现查找偏差，比如数组中就一个元素[3]，让查找5的位置，理应返回1，但是此时会输出成0，
对于坑点3，主要应用在如果数组中有重复元素，需要判断其具体要返回什么位置。
对于坑点,5，如果i不加1的，比如i = 0，j= 1 的情况，会出现mid = 0然后一直死循环下去
对于坑点4，依据right能不能取到而定，如果right可以取到则，right必须要-1，不减1的话，还是会出现i = j时的死循环。
https://segmentfault.com/a/1190000011283470
