二分查找的秘密

学习于Leetcode

文章目录

• 二分查找的秘密
• 前言
• 一、二分查找是什么？
• • 33. 搜索旋转排序数组
• 二、高级用法
• • 寻找旋转排序数组中的最小值
• 三、最高级用法
• • 找到 K 个最接近的元素
• 总结
• • 第一点
  • 第二点

前言

一、二分查找是什么？

这是最常见也是大家一开始从书本上第一次学习到二分查找的样子，
在一个有序数组内查找某一个值是否存在其中

int search(vector& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right){int mid = (right + left) / 2;//为了防止（left + right）overflow 可以用(left - right) / 2 + leftif (nums[mid] < target){left = mid + 1;} else if (nums[mid] > target){right = mid - 1;} else {return mid;}}return -1;}

33. 搜索旋转排序数组

整数数组 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) 的算法解决此问题。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:int search(vector& nums, int target) {//logN则先想到二分//关键：旋转之后，利用二分，一定可以将数组分为一个有序一个无序的，再在无序的部分上分还是一个有序一个无序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 = (r - l) / 2 + l;if (nums[mid] == target) {return mid;}if (nums[0] <= nums[mid]) {//左半区域有序，直接查找即可if (nums[0] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {//左半无序则右半有序if (nums[mid] < target && target <= nums[n - 1]) {l =mid + 1;} else {r = mid - 1;}}}return -1;}
};

二、高级用法

区别于第一种经典的用法，这种题目倾向于二分比较到最后一步，而非中途找到target便退出,例如求最值，符合某一条件的最小值等等
题目中的有序条件或许是隐藏的

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

已知一个长度为 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) 的算法解决此问题。

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/binary-search/xeawbd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:int findMin(vector& nums) {//同样此数组仍然一半有序一半无序,升序部分最左最小，无序部分再分int l = 0, r = nums.size() - 1;int n  = nums.size();while (l < r) {int mid = (r - l) / 2 + l;if (nums[mid] < nums[n - 1]) {//若右半有序则最小值在0~mid之间r = mid;} else {//若右半无序则mid~n-1之间一定有最小值l = mid + 1;}}return nums[l];}
};

三、最高级用法

这第三种需要判断当前索引mid的左右相邻元素来判断区间左右走向
第一种经典用法只需要比较mid即可
第二种需要比较mid一侧相邻元素来决定走向

找到 K 个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
示例 2：

输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/binary-search/xeve4m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:vector findClosestElements(vector& arr, int k, int x) {//先找到数组中不小于x的第一个位置，左右依次比较寻找区间int l = 0, r = arr.size() - 1;while (l < r) {int mid = (r - l) / 2 + l;if (arr[mid] < x) {l = mid + 1;} else {r = mid;}}int right = l;int left = l - 1;while (k--) {if (left < 0) {right++;} else if (right >= arr.size()) {left--;} else if (x - arr[left] <= arr[right] - x) {left--;} else {right++;}}return vector (arr.begin() + left + 1, arr.begin() + right);}
};

总结

关键在于，边界如何确定，二分区间如何走向（是判断左向、右向、还是两个都判断），以及区间地开闭如何判断,主要有以下几处细节注意

int search(vector& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right){//第一、这里到底什么时候带等号？int mid = (right + left) / 2;//if (nums[mid] < target){left = mid + 1;//第二、这里left到底加不加一} else if (nums[mid] > target){right = mid - 1;//这里right到底减不减一} else {return mid;}}return -1;}

第一点

while ()这一判断条件其实就是循环结束的条件
while (left <= right) 意味着结束条件是left > right，即这时候，剩余搜索区间为空
while (left < right) 意味着结束条件是left = right, 即这时候，剩余搜索区间内只剩下mid = left = right这一个元素

有的时候我们需要找到target，那么在找到的情况下直接返回mid；
有的时候我们找不到target，则while (left <= right) 结束之后返回-1；
有时候我们需要找到target的最小或最大位置，就不能简单直接结束循环返回，而是要循环到最后一步while (left < right) 返回left``

第二点

对于搜索区间 [left,right] 左闭右闭，在检查完mid的值以后，便将搜索区间分为了[left,mid - 1] 和 [mid + 1,right] 两个闭区间
而对于要找到target的最小位置，则当mid的元素大于等于target时，说明 [left,mid] 闭区间为下一步搜索区间，而若mid的元素小于target时，则 [mid + 1,right]为搜索区域，也即 (mid,right] 左开右闭区间。
由此可见，区间端点是否需要再一次搜索，是mid是否加一的关键。