二分查找

题单中前4题为必做。 在一个长度为n的数组里，如果要找到一个值所在的位置，那么必须把整个数组枚举一遍才能找到。但是枚举一遍要计算n次，非常的慢。 如果想要在一个长度为n的升序（元素从小到大排好）数组里，找到值x所在的位置，就不必枚举所有数。 平时我们在用词典查单词的时候，我们随手翻一页。如果这一页的单词首字母比想要找的单词小，那么你就会往后翻，否则就往前翻。如此循环，一步一步缩小范围，直到找到为止。 这就叫做二分查找。我们也可以将这种方法运用到升序数组里。 一开始在[1,n]的范围里查找，先看看中间位置的值跟x的大小关系，如果小于x则找后面一半，否则找前面一半。直到找到为止。 更抽象的来说，如果要在一个区间[1,n]里面找满足某条件（比如大于等于x）的第一个数。且前面所有数不满足该条件，后面所有数满足该条件，中间有一个分界点（可能全都满足或者全都不满足）。那么就可以用二分查找。 ``` int l=0,r=n+1;//l永远不满足条件，r永远满足条件 while(l+1<r){//直到l和r差1再停止 int mid=(l+r)/2;//判断中间位置能使得该算法在最坏情况下最快 if(check(mid))//判断mid是否满足条件 r=mid;//往前找 else l=mid;//往后找 } //那么循环完后，r就是第一个满足条件的数 //check函数根据题目要求来修改 ```