随手笔记：二分查找
写作业的时候遇到一道需要进行二分查找的编程题目，在PTA上总是有测试用例不通过，纠结了好久。
关于二分查找，原理很简单，我起初也认为只要理解了原理写出代码并不难；但当你真正开始写的时候，就会发现事实并非如此。
我在贝尔实验室和IBM的时候都出过这道考题。那些专业的程序员有几个小时的时间，可以用他们选择的语言把上面的描述写出来；写出高级伪代码也可以。考试结束后，差不多所有程序员都认为自己写出了正确的程序。于是，我们花了半个钟头来看他们编写的代码经过测试用例验证的结果。几次课，一百多人的结果相差无几：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。 我很惊讶：在足够的时间内，只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人：高德纳在《计算机程序设计的艺术 第3卷 排序和查找》第6.2.1节的“历史与参考文献”部分指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。 ”——乔恩·本特利，《编程珠玑》
从上面的内容可以看到，二分查找是名副其实的陷阱。
给定一个有序的数组，查找某个数是否在数组中。用二分查找的话，搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
二分查找用伪代码描述大致如下：
left = 0, right = n-1, position = -1
while(left<=right){
mid = (left + right)/2
if A[mid]<X: left = mid + 1;
else if A[mid]>X: right = mid - 1;
else position = mid;
}
return position;
按照上面的伪代码编写二分查找的程序基本就是正确的。我们先给出正确的代码样例：
int search(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n - 1;//注意点1
while (left <= right) //注意点1
{
//注意点2
middle = left + (right - left) / 2;
if (array[middle] > v)
right = middle - 1;//注意点1
else if (array[middle] < v)
left = middle + 1;//注意点1
else
return middle;
}
return -1;
}
这里我们先看注意点①：
如果不注意这几处地方的一致性很容易导致死循环，一般来说有这样的要点可以把握遵循
如果，right=n-1 => while(left <= right) => right=middle-1;
如果，right=n => while(left < right) => right=middle;
-
1.
<=的情况while (left <= right) { middle = left + (right - left) / 2; if (array[middle] > v) right = middle - 1; else if (array[middle] < v) left = middle + 1; else return middle; }
对于第一种<=的情况，我们可以将其称为左闭右闭区间。因为<=的存在每次搜索目标值时，都是在一个左右两端都可以取到的范围内查找。
比如，若array[mid]<V，那么array[0]<=array[1]<=...<=array[mid]<V。因此，V不可能存在于array[0...mid]中的任何位置。显然，这时查找的区间应该落在array[mid+1...n-1]之间，left=mid+1。
同理，array[mid]>V时应该在array[0...mid-1]之间寻找，right=mid-1。
- 2.
<的情况
while (left < right)
{
middle = left + (right - left) / 2;
if (array[middle] > v)
right = middle;
else if (array[middle] < v)
left = middle + 1;
else
return middle;
}
对于第二种<情况，我们可以将其称为左闭右开区间。因为<的存在每次在搜索目标时，都是在一个左端可以取到但右端取不到的范围内查找，即[ )。
正因为右边的值取不到，所以在给right赋值时right=n，确保array[n-1]也在搜索的范围内。
比如，若array[mid]<V，那么V不可能存在于array[0...mid]中的任何位置，查找区间变更为array[mid+1...n-1]，left=mid+1；
若array[mid]>V，那么V不可能存在于array[mid...n-1]中的任何位置，应该在array[0...mid-1]之间查找。但要注意的是，我们这里的判断条件是left<right左闭右开区间，所以right=mid使得搜索范围array[0...mid)刚好将array[0...mid-1]包括。
再看注意点②：
如果middle= (left+right)/2; 当left与right的值比较大的时候，其和可能溢出。
