首页 来点算法

# 二分法

  1. 在一个有序数组中找一个数是否存在。
  2. 在一个有序数组中，找 >= 某个数最左侧的位置。
  3. 局部最小值问题（局部最小：在无序、任意两个相邻的数不相等的数组中，有局部最小定义：如果 0 位置的数小于 1 位置的数，那么 0 称做局部最小，如果位置 N-1 小于 N-2 上的数，那么 N-1 上的数称为局部最小，在相邻的三个数中，中间那个数最小，则这个数叫局部最小。 额好像就是极小值点）。

二分法一般用于有序数组中。

二分法有两种表现形式

  • 闭区间 [left,right]，这时的 while (left <= right) 要使用 <= ，因为 left == right 是有意义的，所以使用 <=。 right = nums.size() 。

    if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个 nums [middle] 一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1

  • 左闭右开 [left, right)，这时的 while (left < right) ，这里使用 <, 因为 left == right 在区间 [left, right) 是没有意义的。

    if (nums[middle] > target) right 更新为 middle，因为当前 nums [middle] 不等于 target，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right 更新为 middle，即：下一个查询区间不会去比较 nums [middle]

  • 35. 搜索插入位置

  • 704. 二分查找 - 力扣（LeetCode）

  • 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

  • 69. x 的平方根 - 力扣（LeetCode）

  • 367. 有效的完全平方数 - 力扣（LeetCode）

# 34

class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        int rightBoarder = rightBorder(nums, target);
        int leftBoarder = leftBorder(nums, target);
        // 情况一
        if (leftBoarder == -2 || rightBoarder == -2)
        {
            return {-1, -1};
        }
        // 情况二
        else if (rightBoarder - leftBoarder > 1)
        {
            return {leftBoarder + 1, rightBoarder - 1};
        }
        // 情况三
        else
        {
            return {-1, -1};
        }
    }
private:
    int leftBorder(vector<int> &nums, int target)
    {
        // 这里可以等于 - 2，-3，-4 等等。
        int left = 0, right = nums.size() - 1, leftBoarder = -2;
        while (left <= right)
        {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] >= target)
            {
                right = mid - 1;
                leftBoarder = right;
            }
            else
            {
                left = mid + 1;
            }
        }
        return leftBoarder;
    }
    int rightBorder(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1, rightBoarder = -2;
        while (left <= right)
        {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] <= target)
            {
                left = mid + 1;
                rightBoarder = left;
            }
            else
            {
                right = mid - 1;
            }
        }
        return rightBoarder;
    }
};

这里主要是分三种情况

  • 情况一：target 在数组范围的右边或者左边，例如数组 {3, 4, 5}，target 为 2 或者数组 {3, 4, 5},target 为 6，此时应该返回
  • 情况二：target 在数组范围中，且数组中不存在 target，例如数组 {3,6,7},target 为 5，此时应该返回
  • 情况三：target 在数组范围中，且数组中存在 target，例如数组 {3,6,7},target 为 6，此时应该返回

主要把它分成三种情况就好理解了。

# 69:

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

x 的平方根可以利用二分法，从一开始，跟二分法差不多。

x / mid >= mid 防止栈溢出，别问我怎么知道的，因为我用 (mid * mid) <= x 的时候给我报栈溢出的错。

只要检测到 mid 的平方比 x 小或者等于 x 的时候就可以将这个值存起来，防止之后的 mid 变大。

也可以用牛顿迭代法。

# 367

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 1, right = num;
        while (left <= right) {
            // 这里用 int 的话不够准确
            // 5 / 2 == 2 显然不对
            double mid = left + ((right - left) >> 1);
            if (num / mid == mid) {
                return true;
            } else if (num / mid < mid) {
                right = mid - 1; 
            } else if (num / mid > mid) {
                left = mid + 1;
            }
        }
        return false;
    }
};

和 69 题差不多，只是把判断条件细化了，和把 mid 改用 double。

要是不改的话会有误差，因为两个数整除会舍去小数。69 题因为找不到平方根的话可以返回一个近似的值，所以可以不用 double。

也可以用牛顿迭代法。