二分查找是刷题重要的一环，在leetcode较多题目都可以用二分查找解决。二分查找基本思想如下： 对一个有序的数据集合，查找的思想类似分治思想，每次通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。
题目：leetcode-704. 二分查找
/** * 注意在实现的时候： * 1、循环终止条件： low <= high * 2、mid的取值，假如low和high比较大的话，取 (low + high) / 2， * 容易发生溢出，改进的写法 low + (high - low) / 2， * 进行性能优化的话，可以写成：low + ((high - low) >> 1) * 3、low和high的更新 * low = mid - 1; high = mid + 1，假如low == high，并且在mid位置不等于 value， * 那么容易造成死循环。 * */ int bsearch(vector<int> &vec, int val){ int low = 0; int high = vec.size() - 1; // 查找指定元素 while(low <= high){ int mid = low + ((high -low) >> 1); if(vec[mid] == val){ return mid; } else if(vec[mid] > val){ high = mid - 1; }else if(vec[mid] < val){ low = mid + 1; } } return -1; }求平方根
leetcode 69. x 的平方根 套用上面模板，求平方根AC代码如下：
class Solution { public: int mySqrt(int x) { int low = 1; int high = x / 2; if(x == 0 || x == 1) return x; while(low <= high) { int mid = low + ((high -low) >> 1); if(x / mid == mid ) { return mid; } else if(x / mid > mid) { low = mid + 1; } else { high = mid - 1; } } return high; } };leetcode 278. 第一个错误的版本 这道题也是最简单的二分题目之一，AC代码如下：
// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1; int high = n; while(low < high){ int mid = low + ((high -low) >> 1); if(isBadVersion(mid)){ high = mid; } else { low = mid + 1; } } return low; } };