C++ 二分查找模板和leetcode原题示例

    科技2022-07-20  104

    二分查找

    二分查找是刷题重要的一环,在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; } };
    Processed: 0.009, SQL: 8