二分查找

二分查找

众所周知，二分查找有两种写法：

while( left <= right)：

    条件声明为：`left = 0, right = nums.size() - 1` ，这个边界对于数组来说是**左闭右闭 **的，在循环体内部直接查找元素，把当前搜索区间分为**三部分**，即 **左 、中、 右**，如果等于中间元素，就直接返回，如果大于中间元素，就去右边的区间找，即 **left = mid + 1**；如果小于中间元素，就去左边的区间找，即 **right = mid - 1**。当 **left > right** 时跳出循环，没有找到，**此时 left 在target的插入点下标（也可以说是第一个大于等于target的下标）**，**right 指向 left - 1 位置**。

// leetcode 35.搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target) 
                right = mid - 1;
            else 
                return mid;
        }
        return left;
    }
};

while (left < right) ：

    条件声明为：`left = 0, right = nums.size()` ，这个边界对于数组来说是**左闭右开 **的，所以**left == right**时候就没意义了，跳出循环。这种写法表示在循环体内部排除元素，把当前搜索区间分成**两个部分**。一部分是不存目标元素的区间，一部分可能存在目标元素的区间。所以当 `target`大于中间元素，取右边，由于左边是闭的，所以 `num[left]` 肯定不是 `target`值，所以 **left = mid + 1**，当 `target` 小于中间元素，取左边，由于右边是开的，`num[right]` 可能是`target` 值，所以**right = mid**。

    当 **left == right **时没有找到，跳出循环，此时 `left`和 `right` 都在 **target的插入点下标（也可以说是第一个大于等于target的下标）**

// leetcode 35.搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
            else  return mid;
        }
        return left;
    }
};

可将后两个判断合在一起

// leetcode 35.搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};

相关题目：

LeetCode704 - 二分查找

704. 二分查找

简单题，原汁原味的二分查找。

LeetCode34 - 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

思路：

学习 liweiwei1419

二分查找算法就一种思想：减而治之（逐渐缩小问题规模），也可以视为「排除法」（一直排除一定不是目标元素的区间，思想依然是逐渐缩小搜索区间）；
根据看到的中间位置的元素的值 nums[mid] 可以把待搜索区间分为两个部分：「一定不存在目标元素的区间」和「可能存在目标元素的区间」。因此mid只可能被分到这两个区间的其中一个，即：while 里面的 if 和 else 就两种写法：
- 如果mid分到左边区间，即区间分成[left..mid]与[mid + 1..right]，此时分别设置 right = mid 与left = mid + 1；
- 如果 mid 分到右边区间，即区间分成 [left..mid - 1]与[mid..right]，此时分别设置 right = mid - 1 与left = mid。
分类讨论的时候，不断排除不是目标元素的区间，以确定下一轮搜索的区间。即一直思考下一轮搜索区间是什么，以左闭右闭区间 的形式表现出来，这样到底变化 left 还是变化 right，加不加 1就会很清楚；
在退出循环的时候。如果区间一定存在目标元素，直接返回left或者right。否则还需要单独做一次判断；
在循环体里，对 nums[mid] 与 target 的大小关系的判断需要分类讨论。
- 这里需要仔细一点，向左走还是向右走结果错了的话会导致整个结果都错。如果写成三个分支去判断；
  最后要合并成两个分支。这样退出循环的时候，left 和 right 才会合并到一起。才可以不用纠结到底返回 left 还是返回 right。
看到边界是 left = mid 的时候，取中间数的计算表达式应该上取整，即在括号里加 1，这是为了防止在区间只有两个元素的时候出现死循环；
当然可以在if 和 else 语句里写出三种情况，但是建议如果真的是分三种情况的话，写完以后需要将其中两种情况合并，否则在退出循环以后，不一定有left == right成立。

二分查找 - 图1

吗class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return {-1, -1};
        return {find_left_target(nums,target),find_right_target(nums,target)};
    }

    int find_left_target(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size()-1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) // 小于一定不是解
                left = mid + 1; // 下一轮搜索区间是 [mid + 1..right]
            else 
                right = mid; // nums[mid] > target，下一轮搜索区间是 [left..mid]
        }
        if (nums[left] == target) return left;
        return -1;
    }

    int find_right_target(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) // 下一轮搜索区间是 [left..mid - 1]
                right = mid - 1;
            else 
                left = mid;  // 下一轮搜索区间是 [mid..right]
        }
        if (nums[left] == target) return left;
        return -1;
    }
};

如果不熟悉二分，可以先写成三种情况再合并为两种，以 find_left_target 为例：

    int find_left_target(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size()-1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) 
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else 
                right = mid
        }
        if (nums[left] == target) return left;
        return -1;
    }

LeetCode35 - 搜索插入位置

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

即LeetCode34 中的 find_left_target

但是需要特判，即如果 target 大于数组的最后一个元素，只能在末尾插入

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        if (nums[len - 1] < target) return len;
        int left = 0, right = nums.size() - 1;
          // 一定有 nums[len - 1] >= target
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};

由于执行到最后nums[left..right] 里一定存在插入元素的位置，退出循环的时候一定有left == right成立，因此返回left或者right都可以。

既然 len 也有可能是答案，可以在初始化的时候，把 right 设置成 len，此时就不需要特殊判断了。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};

LeetCode69 - x 的平方根

69. x 的平方根

注意处理边界，注意平方越界

方法一：二分查找后，如果sqrt_x的平方大于x，返回sqrt_x - 1，否则直接返回sqrt_x

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return x;  // 特判，不能使后面的计算除数为0
        int left = 1, right = x, sqrt_x;
        while (left <= right)
        {
            sqrt_x = left + (right - left) / 2;
            if (sqrt_x  < x / sqrt_x)
            {
                left = sqrt_x + 1;
            }
            else if (sqrt_x > x / sqrt_x)
                right = sqrt_x - 1;
            else break;
        }
        return sqrt_x > x / sqrt_x ? sqrt_x - 1 : sqrt_x;
    }
};

方法二：牛顿迭代法

迭代公式： x_{i+1} = \frac{1}{2}(x_i+\frac{C}{x_i})

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        double x_0 = x, C = x, x_1;
        while(1)
        {
            x_1 = 0.5 * (x_0 + C / x_0);
            if (fabs(x_1 - x_0) < 1e-7)
                break;
            x_0 = x_1;
        }
        return (int)x_0;
    }
};

LeetCode367 - 有效的完全平方数

367. 有效的完全平方数

方法一：二分查找

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 2) return true; 
        int left = 1, right = num/2;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if ((long long )mid * mid < num)
                left = mid + 1;
            else if ((long long )mid * mid > num )
                right = mid - 1;
            else 
                return true;
        }
        return false;
    }
};

方法二：牛顿法

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 2) return true;

        long x = num;
        while (x * x > num)
            x = (x + num / x) / 2;
        return (x * x == num);
    }
};