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

前言

本文的主题是二分查找，通过两道题目讲解，一道是 x 的平方根，一道是山脉数组的封顶索引。题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写。

x 的平方根

题目解析

由题目的要求，我们需要求一个数的平方根，并且舍去小数部分，禁止使用 pow 函数等。说白了就是要我们自己模拟实现一个函数。

这道题的暴力解法很简单，将题目示例的所有平方列举出来，和题目给的 x 一个一个比较。当比较到 x 小于某个数的平方，那么就可以得到 x 等于某个数减 1。

但是这样做的话，时间复杂度就是 O(N)，并且没有利用数据是升序的特点。从 1 开始列举平方，也就是一个升序的过程。

算法原理

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

left < right 是必要的，但因为 ans 区域是在左边，所以 left = mid, right = mid - 1，因为有了减法，所以求中间是 + 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;
        }
         left;
    }
};