二分法, binary search algorithm 二分法 一，学习别人的总结与讲解 本部分的参考见末尾，本部分文字是在其基础上的二度总结 (节约时间和精力）。
典型的二分法 算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。
基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，
如果当前位置arr[k]值等于key，则查找成功；
若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；
若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，
直到找到为止,时间复杂度:O(log(n))。
上面的思想就是最最简单的二分法，即从一个排好序的数组之查找一个key值。 如下面的程序：
int search(int *arr, int n, int key) { int left = 0, right = n-1; while(left<=right) { //慎重截止条件，根据指针移动条件来看，这里需要将数组判断到空为止 int mid = left + ((right - left) >> 1); //防止溢出 if (arr[mid] == key) //找到了 return mid; else if(arr[mid] > key) right = mid - 1; //给定值key一定在左边，并且不包括当前这个中间值 else left = mid + 1; //给定值key一定在右边，并且不包括当前这个中间值 } return -1; } 证明二分算法正确性 循环不变式： 如果key存在于数组中，始终只可能存在于当前的array[left,right]数组段中。
初始化：
第一轮循环开始之前，array[left,right]就是原始数组，这时循环不变式显然成立。
迭代保持：
每次循环开始前，如果key存在，则只可能在待处理数组array[left, ..., right]中。
对于array[mid]<key，array[left, ..., mid]均小于key，key只可能存在于array[mid+1, ..., right]中；
对于array[mid]>key，array[mid, ..., right]均大于key，key只可能存在于array[left, ..., mid-1]中；
对于array[mid]==key，查找到了key对应的下标，直接返回结果。
显然如果没找到key，下一次继续查找时我们设定的循环不变式依然正确。
死循环否？在前两种情况中，数组长度每次至少减少1 (实际减少的长度分别是mid-left+1和right-mid+1），直到由left==right变为left>right (数组段长度由1-0）—>截止了，所以一定不会死循环。
终止：
结束时发生了什么？left>right,被压缩的数组段为空，表示key不存在于所有步骤的待处理数组，再结合每一步排除的部分数组中也不可能有key，因此key不存在于原数组。因此我们得到了符合要求的解，此算法正确。
如果条件稍微变化一下，还会写吗？其实，二分法真的不那么简单，尤其是二分法的各个变种。
二分法的变种1 数组之中的数据可能可以重复，要求返回匹配的数据的最小 (或最大）的下标；更近一步，需要找出数组中第一个大于key的元素 (也就是最小的大于key的元素的）下标，等等。 这些，虽然只有一点点的变化，实现的时候确实要更加的细心。
下面列出了这些二分检索变种的实现
a. 找出第一个与key相等的元素的位置
快速思考四个问题：
1）通过什么条件来移动两个指针？与中间位置进行大小比较。
当arr[mid]<key时，当前位置一定不是解，解一定只可能在arr[mid+1,high]，即右边
当arr[mid]>key时，当前位置一定不是解，解一定只可能在arr[low,mid-1]，即左边
...