LeetCode二分查找专题

基础知识

二分查找是一种在有序数组中查找特定元素的算法，它通过不断将搜索区间减半来快速定位目标元素。对于搜索区间的定义有三种方式，分别是左闭右闭，左闭右开和左开右开。

这三者之间的主要区别在于以下两点
(1)每次折半的时候两端的坐标应该移到mid的位置上还是多偏移一个元素
(2)while判断结束的条件是 left<right,left<=right,还是left<right-1

• left和right的偏移区别

  • 左闭右闭区间，要找的值比target小，那么right=mid-1，因为mid已经被检查过了，mid-1保证了闭区间不重复，要找的值比target大，那么left=mid+1。
  • 左闭右开区间，要找的值比target小，那么right=mid，保证了右开区间，要找的值比target大，那么left=mid+1。
  • 左开右开区间，要找的值比target小，那么right=mid，要找的值比target大，那么left=mid，这样保证了每次缩小的区间都是左开右开的。

• while判断结束的条件

  • 左闭右闭区间，因为搜索的范围包括区间的两个端点，所以当left=right的时候，搜索的范围仍然存在，所以while判断结束的条件是left<=right。
  • 左闭右开区间，因为搜索的范围包括区间的左端点，不包括区间的右端点，所以当left=right的时候，搜索的范围已经不存在了，所以while判断结束的条件是left<right。
  • 左开右开区间，因为搜索的范围不包括区间的两个断点，所以当left=right-1的时候，搜索的范围已经不存在了，所以while判断结束的条件是left<right-1。

代码如下：

// 左闭右闭区间
int binarySearch(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) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;//缩小范围到[mid+1,right]
        } else {
            right = mid - 1;//缩小范围到[left,mid-1]
        }
    }
    return -1;
}
// 左闭右开区间
int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;//缩小范围到[mid+1,right)
        } else {
            right = mid;//缩小范围到[left,mid)
        }
    }
    return -1;
}
// 左开右开区间 
int binarySearch(vector<int>& nums, int target) {
    int left = -1, right = nums.size();
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;//缩小范围到(mid,right)
        } else {
            right = mid;//缩小范围到(left,mid)
        }
    }
    return -1;
}

为什么使用mid = l + (r - l) / 2
mid = l + (r - l) / 2这个计算方式避免了直接使用(l+ r) / 2可能导致的整数溢出问题。

[!NOTE]
以下代码都在左闭右闭的情况下写。

例题

搜索插入位置

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

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

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

思路：
当目标值不存在时，目标值应该插入在left的位置。
因为当left，right重叠时，mid也在此处：
如果target大于nums[mid]，则left不变，刚好为插入位置，因为nums[left+1]比target大。
如果target小于nums[mid]，则left=mid-1，刚好为插入位置，因为nums[left+1],也就是nums[mid]比target大。

代码：

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) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return left;
    }
};

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

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

提示：
0 <= nums.length <= 105
109 <= nums[i] <= 109
nums是一个非递减数组
-109 <= target <= 109

思路：
查找开始位置：
使用二分查找，调整查找条件，使得找到目标值时，继续向左搜索即right=mid-1，直到找到第一个出现的目标值。
查找结束位置：
使用类似的二分查找，调整查找条件，找到目标值时，继续向右搜索即left=mid+1，直到找到最后一个出现的目标值。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = findLeft(nums, target);
        int right = findRight(nums, target);
    }

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

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

搜索旋转排序数组

题目：
整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

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

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

思路：
考虑left=mid+1的情况
1.nums[0]<=nums[mid]，此时mid一定在前半有序部分。
若target<nums[0]，则一定在[mid+1,right]中寻找。例：[4,5,6,7,8,0,1,2]中mid为7，target为1。
如果nums[0]<target&&target>nums[mid],则一定在[mid+1,right]中寻找。例[4,5,6,7,8,9,1,2]中mid为7，target为9。
2.nums[0]>nums[mid]，此时mid一定在后半有序部分。
则要想向后寻找，不仅要target>nums[mid]，还有target<nums[0]

代码

class Solution {
public:
    int search(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) {
                return mid;
            }
            else if (nums[0]<=nums[mid]&&(nums[mid]<target||target<nums[0])) {
                left = mid + 1;
            }
            else if (nums[0] > nums[mid] && target<nums[0] && target>nums[mid]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

寻找旋转排序数组中的最小值

题目
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到[4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到[0,1,2,4,5,6,7]
  注意，数组 [a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为O(log n) 的算法解决此问题。

示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为[1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为[0,1,2,4,5,6,7]，旋转 4 次得到输入数组。

示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

思路：
此时需要思考何时向左缩小，合适向右缩小。
下面考虑合适向右缩小，即left=mid+1
当最小值在右侧时，一定是mid在前半有序部分，即nums[mid]>nums[0]。注意到可以旋转K次，即没有旋转。那还需nums[0]>nums[nums.size()-1]。故为nums[0] <= nums[mid] && nums[0] > nums[nums.size() - 1]

代码：

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

寻找两个正序数组的中位数

题目：
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

思路：
【LeetCode 每日一题】4. 寻找两个正序数组的中位数 | 手写图解版思路 + 代码讲解_哔哩哔哩_bilibili

代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size() + nums2.size();
        if (n % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, n / 2);
            int right = find(nums1, 0, nums2, 0, n / 2 + 1);
            return (left + right) / 2.0;
        }
        else {
            return find(nums1, 0, nums2, 0, n / 2 + 1);
        }
    }

    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        //保证nums1短，nums2长
        if (nums1.size() - i > nums2.size() - j) {
            return find(nums2, j, nums1, i, k);
        }
        //nums1没有元素
        if (nums1.size() == i)return nums2[j + k - 1];

        if (k == 1)return min(nums1[i], nums2[j]);
        
        //两个数组k/2位置
        int idx1 = min((int)nums1.size(), i + k / 2);
        int idx2 = j + k - k / 2;
        if (nums1[idx1 - 1] < nums2[idx2 - 1]) {
            //丢弃nums1的[i,idx1)
            return find(nums1, idx1, nums2, j, k - (idx1 - i));

        }
        else {
            //丢弃nums2的[j,idx2)
            return find(nums1, i, nums2, idx2, k - (idx2 - j));
        }
    }
};