在一个有序的序列中查找某一个数值，我们可以用传统的for循环，时间复杂度是O(n)，但是很明显没有充分利用序列有序这个条件。
根据有序这个条件，我们可以每次都选取序列的中间值作为标准，来决定我们下一步的区间选择，这样实现的二分查找，时间复杂度缩减为O(logN)。
注意：二分查找写法不谨慎，很容易出现死循环，以下版本注意几个问题： 1. while循环的退出条件是 l != r ，也就是说最终 l 是会等于 r 的，但是 l 这个位置不一定是查找的对象，因为可能根本就不存在这个元素，所以最终答案还需要再特判下 l 这个位置是否正确。 拿下面的例子来说，如果查找元素不存在，l 最终会停在最大的小于target的位置。 2. l 和 r 的变化要注意，如果条件满足，这个时候正确答案可能是mid，所以 l = mid ，要包含mid ； 如果条件不满足，那么 r = mid - 1 ，mid肯定不是答案，所以可以减一，不用包含 mid 。
class Solution { public: int search(vector<int>& nums, int target) { int l=0, r=nums.size()-1; while (l!=r){ int mid=(l+r+1)/2; if (nums[mid]<=target) l=mid; else r=mid-1; } if (nums[l]==target)return l; else return -1; } };如果代码第7行的判断条件改为 if nums[mid]<target l=mid+1; else r=mid; 是否可以呢？？ 虽然逻辑上很通顺，但是实际上不可以！ 二分查找陷入死循环，往往在 l 和 r 相邻的情况。如上改动，mid=(l+r+1)/2. 如果 r=l+1， 那么mid=r。 而判断条件满足的话，l=mid+1，也就是l=r。 完成查找。 但是如果判断条件不满足，执行的是r=mid，也就是没有改变。 所以这里就会陷入死循环。
总结：
上面的写法 mid=(l+r+1)/2 和后面的判断条件是一个整体。他们共同作用使得二分查找不会陷入死循环。 你也可以构建出自己的不会陷入死循环的整体，也可以记住一个模板，一直用这个模板。 重要的是，要学会判断二分查找会不会死循环，判断的方法就是上述的r=l+1的情况，看看能不能跑出来。
将一个求解的问题，变成一个已知答案的判断问题。适合那些求解很难，但是判断容易的题目。
明显的特征就是求最大值最小，最小值最大这种。
