二分查找算法实战：求平方根与山脉数组峰值

x 的平方根

题目解析

题目要求计算一个数的算术平方根，并舍去小数部分，禁止使用 pow 函数等内置库。即需要模拟实现该函数。

暴力解法是将所有平方列举出来与 x 比较。当发现某个数的平方大于 x 时，结果即为该数减 1。此方法时间复杂度为 O(N)，未利用数据升序特性。

算法原理

利用二段性将数分为小于等于 x 和大于 x 的区域，目标区域是小于等于 x 的右端点。因此使用非朴素求左端点的二分模板。

循环条件为 left < right。由于 ans 区域在左边，更新规则为 left = mid, right = mid - 1。为避免死循环，mid 计算需加 1。

算法编写

class Solution {
public:
    int mySqrt(int x) {
        if(x <= 0) return 0;
        int left = 1, right = x;
        while(left < right) {
            long long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

注意两点：一是 x 可能为 0，直接返回 0；二是 mid * mid 可能导致数据溢出，需使用 long long 类型。

山脉数组的封顶索引

题目解析

题目要求在山脉数组中找到最高值的索引。暴力解法判断后一个值是否小于当前值即可，时间复杂度 O(N)。但题目要求 logN 解决方案，故采用二分查找。

左右端点不可能是结果，left 从 1 开始，right 从 nums.size() - 2 开始。

算法原理

寻找二段性：峰值左边 arr[i] > arr[i - 1]，右边同理。答案位于左侧区域，使用非朴素求左边的二分模板。

算法编写

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = , right = arr.() - ;
        (left < right) {
             mid = left + (right - left + ) / ;
            (arr[mid] > arr[mid - ]) left = mid;
             right = mid - ;
        }
         left;
    }
};