代码随想录day1-二分查找_代码随想录 二分查找

代码随想录day1-二分查找

1、LeetCode 704 二分查找

题目描述：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4    
1
2
3

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1  
1
2
3

题目分析：
关于这种二分查找的题目，本质上都是可以用暴力方法求解的，就是从头到尾直接遍历就行了。但是随着数据量的增大，暴力算法往往会面临超时的情况，所以需要使用更高效的查找方法。

二分法就是一种高效的查找算法。
对于二分查找的题目，存在如下几个特征：
1. 列表（数组）是有顺序的；
2. 题目还要强调有无重复元素。

二分查找的难点以及容易混淆的地方主要是两个点，即循环体内部的条件，到底是while (left < right)呢还是while (left <= right)呢，以及边界的改变条件是left = mid还是left = mid + 1呢？接下来我将根据这一道题对这两种情况进行分析。

题目解答：
方法一：使用二分查找，循环内部为left <= right，相当于是一个左闭右闭的区间[left, right]。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 使用二分法进行查找，使用左闭右闭的区间
        int left = 0;  // 设置左边界为0
        int right = nums.size()-1;  // 设置右边界，将数组设置为左闭右闭
        while(left <= right){  // left == right 是有意义的，即一个元素
            // int mid = (left + right) / 2;
            int mid = left + (right - left) / 2;  // 这个写法可以避免溢出，与上面的写法等效
            if(nums[mid] < target)
                left = mid + 1;  // 如果nums[mid] < target, 说明中心点在target的左边，并且说明mid肯定不是需要的点，我们对left进行更新的时候，肯定就随之加1了
            else if(nums[mid] > target)
                right = mid - 1;  // right的更新也是一样的道理
            else
                return mid;  // 如果既不是大也不是小，那么这个mid我们需要查找的值，返回即可
        }
        return -1;  // 如果什么都没查到，就返回-1
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法二：使用二分查找，循环内部为left < right，相当于是一个左闭右闭的区间[left, right)。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 使用二分法进行查找，使用左闭右开的区间
        int left = 0;
        int right = nums.size();  // 这里右边区间的值就设置为元素的个数，相当于是开区间
        while(left < right){  // 此处需要写成<，因为=是没有意义的
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
                left = mid + 1;  // 很明显，mid肯定不是target，需要加1
            else if(nums[mid] > target)
                right = mid;  // 因为右边是开区间，所以这里不需要进行mid-1
            else
                return mid;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

以上两种方法就是我们常用的二分法的查找算法，当循环体内部的内容不一致时，我们更新左右边界的方法也就有所差异。
在以后做题的过程中，我们推荐使用方法，即左闭右闭的方法来做题。

下面是这个题的一般解法：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 使用最一般的方法
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == target)
            return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11

2、LeetCode 35 搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

输入: nums = [1,3,5,6], target = 5
输出: 2

输入: nums = [1,3,5,6], target = 2
输出: 1

输入: nums = [1,3,5,6], target = 2
输出: 1
1
2
3
4
5
6
7
8

题目分析：
本题就是一个典型的二分查找的题目，唯一不同的就是查找找不到的时候，需要返回将按顺序插入的位置。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 其实就是一个二分查找的问题
        int left = 0;
        int 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;  // 最后这个left其实就是最终的需要插入的位置了
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

题目描述：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

输入：nums = [], target = 0
输出：[-1,-1]
1
2
3
4
5
6
7
8

题目分析：
本题初看也是一个查找的问题，查找的是一个重复元素在数组中的头尾位置，但是我们之前提到的二分法的适用背景是不能有重复的元素，所以这个题目不能用简单的二分法进行求解，需要改进一下。

本题存在三种情况：

1. 第一种，需要查找的target在数组的左边或者右边范围外面，即nums = [2, 4, 5]，但是target = 1 或者target = 6，此时返回[-1, -1]。
2. 第二种，需要查找的target在数组的范围中间，但是数组里面没有该元素，即nums = [1, 2, 4]，而target = 3，此时也返回[-1, -1]。
3. 第三种，就是正常的情况。

针对上述的情况，我们有下面的思路，二分法本质上是一种排除法，本题需要查一个元素的起始位置，我们就 可以逐一排除左右两边不是target的元素，就会考虑到查找边界的问题，这里就牵涉到需要查左边界和右边界。

题目解答：
右边界查找：

int getRightBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;  // 定义target在左闭右闭的区间里面，即[left, right]
    int rightBorder = -2; // 没有没赋值的右边界值
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;  // 使用二分法对right和left不断更新
            rightBorder = left;
        }
    }
    return rightBorder;  // 此处的left就是右边界，不包括target的右边界，注意是不包括target的！！！
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

为了加深对这个代码的理解，我这里举一个例子。

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
1
2

最开始，left = 0, right = 5
满足条件进入循环，计算得到mid = 2
此时(nums[2] == 7) < (target == 8)则进入else中，left = 3，此时rightBorder = left = 3
接下来，由于left <= right，进入下一次循环，计算得到mid = 4
此时(nums[4] == 8) == (target == 8)则进入else中，left = 4，此时rightBorder = left = 4
接下来，由于left <= right，进入下一次循环，计算得到mid = 4
此时(nums[4] == 8) == (target == 8)则进入else中，left = 5，此时rightBorder = left = 5
接下来，由于left <= right，进入下一次循环，计算得到mid = 5
此时(nums[5] == 10) > (target == 8)则进入if中，right = 4
由于left > right，不满足循环条件，于是结束循环，很明显，此时rightBorder就是5，是不包括target的！

左边界查找：

int getLeftBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int leftBorder = -2; // 没有没赋值的左边界值
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
            leftBorder = right;
        }
    }
    return leftBorder;  // 注意这里的right就是右边界，是不包括target的右边界！！！！
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这里左边界和有边界一样的确定方法，都是不包含target的左边界。

主函数

vector<int> searchRange(vector<int>& nums, int target) {
    // 一共存在三种情况
    // 1、需要查找的target直接超出了数组的左右范围，这种情况直接无法进入二分查找的代码
    // 2、需要查找的target在数组的左右范围中，但是数组中没有
    // 3、需要查找的target在数组的左右范围中，并且可以查到

    int rightBorder = getRightBorder(nums, target);
    int leftBorder = getLeftBorder(nums, target);

    // 第一种情况，直接没有进入数组
    if (rightBorder == -2 || leftBorder == -2) return {-1, -1};

    // 第三种情况，也就是正确的情况
    // 由于是没有包含target的左右边界，所以二者的差值肯定大于2，注意是不包括左右边界的！
    if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};

    // 第三种情况
    else return {-1, -1};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4、LeetCode 69 x的平方根

题目描述：
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

输入：x = 4
输出：2

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
1
2
3
4
5
6

题目分析：
计算平方根是高中数学有名的二分法查找的题目，所以我们这里也可以使用二分查找来处理这个问题。

题目解答：

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if ((long long)mid * mid <= x) {  //  为了防止数据溢出，这里需要用long long 接收数据
                // long的范围为-2^64-1~2^64-1，根据这个题，需要使用long long
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5、LeetCode 367 有效的完全平方数

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
1
2
3
4
5
6
7

题目分析：
典型的二分查找问题，只是需要注意数据长度的问题，防止越界。

题目解答：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 其实就是一个二分查找的问题
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            else {
                return mid;
            }
        }
        return left;  // 最后这个left其实就是最终的需要插入的位置了
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

今天主要学习了二分法查找的问题，属于简单题，day1打卡成功！
患难及困苦，是磨炼人格的最高学府。——苏格拉底