首页 > 代码库 > 二分查找学习
二分查找学习
数组在有序的情况查找某元素，用二分查找可以达到logn的时间复杂度。二分查找虽然看似容易，想要把这个算法完全写好，并灵活运用确并非易事儿。据说专业的程序员有90%的人无法正确实现。如果你不信，不妨自己动手试一试，然后用一些测试用例测一下。
二分查找的思想：在有序数组A[n]中查找x，令s=0,e=n-1，我们先相信x在[s,e]区间，m=(s+e)/2为中间坐标，如果正好x=A[m]则找到输出；如果x<A[m]，则x出现m的左边，反之出现在m的右边。这样每次都可以缩小查找范围，当s>e时未找到则没出现，返回-1。
根据思想不难写出以下代码：
int binarySearch(int A[],int n,int x){ int s = 0; int e = n-1; while(s<=e) { int mid = (s+e)>>1; if(A[mid]<x) s = mid + 1; else if(A[mid]>x) e = mid - 1; else return mid; } return -1;}
注：上述代码如担心s+e溢出的话，可以采用 mid = s + (e-s)>>1;
上述实现较容易，且不容易出错。另外的几种变体使用起来就要小心了。
变体1：
int binarySearch1(int A[],int n,int x){ int s = 0; int e = n; while(s<e) { int mid = (s+e)>>1; if(A[mid]<x) s = mid + 1; else if(A[mid]>x) e = mid; else return mid; } return -1;}
这种方法采用的是右边开区间的边界（不包含）。那么注意当A[mid]>x时，修改结束坐标e时，同样的要不包含右边界，即e=mid。
变体2：
如果数组中有多个满足条件的元素，在算法1中我们随机的找出了一个位置。在《编程珠玑》中给出了一种方法，可以找到第一个满足条件的位置
//找出第一个满足条件的元素xint getFirst(int A[],int n,int x){ int s = -1; int e = n; while(s+1!=e) //s<e && A[s]<x<=A[e] { int mid = (s+e)>>1; if(A[mid]<x) s = mid; else e = mid; } if(e>=n || A[e]!=x) e = -1; return e;}
这种方法可能不太好理解，至少我第一读到的时候就纳闷为什么要这么写呢（没办法，脑袋转的慢呀!-!）。后来想了想终于想通了：因为是要找第一个满足的，那我们在某次判断时，无论当前的是不是要找的都要缩小范围是吧，关键是在找到了“它“，把它分到哪部分好呢？肯定是右半部份啦，因为这样他就变成火车头了。
同理，我们可以得出找到最后一个位置的方法：
//找出最后一个满足条件的元素x位置int getLast(int A[],int n,int x){ int s = -1; int e = n; while(s+1!=e) //s<e && A[s]<=x<A[e] { int mid = (s+e)>>1; if(A[mid]>x) e = mid; else s = mid; } if(s<=0 || A[s]!=x) s = -1; return s;}
另外还有其他各种变种，如找到第一个大于给定元素的位置，找出第一个小于给定元素的位置，找出第一个大于等于给定元素的位置等等，看起来都差不多，写起来还真没那么容易，今天写到这里，后面几个随后再补充吧。也欢迎小伙伴们在评论中指正和补充～
二分查找学习