Leetcode 3.7

二分查找

1.搜索插入位置

搜索插入位置
考虑这个插入的位置 pos，它成立的条件为：

nums[pos−1] < target ≤ nums[pos]
其中 nums 代表排序数组。由于如果存在这个目标值，我们返回的索引也是 pos，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于 target 的下标」。

问题转化到这里，直接套用二分法即可，即不断用二分法逼近查找第一个大于等于 target 的下标 。下文给出的代码是笔者习惯的二分写法，ans 初值设置为数组长度可以省略边界条件的判断，因为存在一种情况是 targe 大于数组中的所有数，此时需要插入到数组长度的位置。

第一点：right一定在left的左面（紧邻），这是由while条件决定的，否则是跳不出来的。
第二点：right右侧数必然是 >= target的，left左侧数必然是 < target的，，这是由于if条件判断加上left，right的移动引起的。
最后，因为我们要找的是插入位置，就是某位置a左面都小于target，右面（包括a）都大于等于target，那么a就是我们要找的位置。不管你是存在还是不存在，都是这个位置。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n- 1, ans = n;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] >= target) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.二分查找

二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (target == nums[mid]) return mid;
            if (target < nums[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.搜索二维矩阵

把二维数组简化为一维数组，继续用二分

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        vector<int> ans;
        int n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans.push_back(matrix[i][j]);
            }
        }
        int len = n * m;
        int l = 0, r = len - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (ans[mid] < target) {
                l = mid + 1;
            } else if (ans[mid] > target) {
                r = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

有意思的一点就是，不用真正的把数组扁平化，可以用这个来代替int x = matrix[mid / n][mid % n];

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        vector<int> ans;
        int n = matrix.size(), m = matrix[0].size();
        int len = n * m;
        int l = 0, r = len - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (matrix[mid / m][mid % m] < target) {
                l = mid + 1;
            } else if (matrix[mid / m][mid % m] > target) {
                r = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这样空间复杂度能减少到 o(1)。

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

在排序数组中查找元素的第一个和最后一个位置
寻找target在数组里的左右边界，有如下三种情况：

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

代码随想录题解

一个寻找左边界，一个寻找右边界

class Solution {
public:
	//找右边界
    int searchRight(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1, rans = INT_MIN;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
                rans = l;
            }
        }
        return rans;
    }
    //找左边界
    int searchLeft(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1, lans = INT_MIN;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] >= target) {
                r = mid - 1;
                lans = r;
            } else {
                l = mid + 1;
            }
        }
        return lans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);
        if (left == INT_MIN || right == INT_MIN) return {-1,-1};
        if (right - left > 1) return {left + 1, right - 1};
        return {-1, -1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

5.搜索旋转排序数组

搜索旋转排序数组

1）二分可以在有序数列进行查找，该数列在某未知点进行旋转，则首先应该找到部分有序数列（总有一侧是有序的数列）；
2）在有序一侧进行查找，若无，则将改变mid位置。以右侧有序为例，若target>nums[mid]且target<nums[nums.size()-1]则在右侧继续二分查找；
3）否则，更改查找范围，right=mid-1，并重复1）-2）。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        if (n == 0) return -1;
        if (n == 1) return nums[0] == target ? 0 : -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < nums[l])  {
                //右半部分是有序的
                //在右侧，右侧二分
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else {
                //左半部分是有序的
                //在左半部分内
                if (nums[l] <= target && target < nums[mid]) {
                    //在左半部分搜索
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return - 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Question

Q1: int mid = l + (r - l) / 2; 为什么不能写成 int mid = (r + l) / 2;
这是因为 (r + l) / 2 存在一个潜在的问题，特别是当 l 和 r 很大时，可能会导致整数溢出。

Q2: nums[mid] >= nums[l] 和 nums[mid] > nums[l]的区别到底是什么，为什么有时候 l = mid + 1; 有时候l = mid;
704.二分查找