力扣DAY63-67 | 热100 | 二分：搜索插入位置、搜索二维矩阵、排序数组查找元素、搜索旋转排序数组、搜索最小值

前言

简单、中等 √ 二分法思路很简单，但是判断边界太麻烦了！难道真的要去背模板吗

搜索插入位置

我的题解

循环条件左不超过右，目标大于中间值（向下取整）时，左=中+1，小于，右=中-1，否则直接返回mid，出循环后返回left。

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

官方题解

官解的条件：目标大于中间值时left也++，最后返回left

心得

标准的就是简洁优雅！不对称的原因在于求mid也是不对称的：向下取整。

搜索二维矩阵

此题之前做过一模一样的，不赘述。

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

我的题解

用二分法查找到这个元素之后，向两边扩展直到不等于目标值为止。

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

官方题解

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标，但这个方法的时间复杂度为 O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 target 开始和结束位置，其实我们要找的就是数组中「第一个等于 target 的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）。

二分查找中，寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标，寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 nums 数组中二分查找 target 的位置，如果 lower 为 true，则查找第一个大于等于 target 的下标，否则查找第一个大于 target 的下标。

最后，因为 target 可能不存在数组中，因此我们需要重新校验我们得到的两个下标 leftIdx 和 rightIdx，看是否符合条件，如果符合条件就返回 [leftIdx,rightIdx]，不符合就返回 [−1,−1]

class Solution { 
public:int binarySearch(vector<int>& nums, int target, bool lower) {int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}vector<int> searchRange(vector<int>& nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {return vector<int>{leftIdx, rightIdx};} return vector<int>{-1, -1};}
};

心得

原来我的题解在极端情况下不是log（n），例如整个数组都是target的情况下。所以还是官解好一点（其实也不一定，n不一定比2log（n）大）。anyway其实官解先定义一个函数找目标值，不同的是多定义了一个bool变量控制right指针的移动/等号条件，当bool为true时，找的是第一个大于等于target的位置，false时找的时第一个大于target的位置。仔细想还挺有意思！

搜索旋转排序数组

我的题解

事实上我是先写了寻找最小值再写这题。找到了最小值坐标后相当于找到了两段有序数组，分别对两段有序数组进行二分查找即可。

class Solution {
public:int findtarget(vector<int> nums, int left, int right, int target){int mid;while(left < right){mid = (right - left)/2 + left;if (target > nums[mid]){left = mid + 1;}else if (target < nums[mid]){right = mid - 1;}else{left = mid;break;}}if(nums[left] == target)return left;elsereturn -1;}int search(vector<int>& nums, int target) {int n = nums.size();int low = 0;int high = n - 1;int mid = ((high - low)>>1) + low;while (low < high){mid = ((high - low)>>1) + low;if (nums[mid] < nums[high]){high = mid;}else if (nums[mid] > nums[high]){low = mid + 1;}else{break;}}return max (findtarget(nums, low, n-1, target), findtarget(nums, 0, low-1, target));}
};

官方题解

对于有序数组，可以使用二分查找的方法查找元素。

但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

class Solution {
public:int search(vector<int>& nums, int target) {int n = (int)nums.size();if (!n) {return -1;}if (n == 1) {return nums[0] == target ? 0 : -1;}int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) / 2;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是否在这个区间内，如果在则把一边的边界移到这个区间中，否则把两个边界都移出区间并重复上述步骤。此题重点在于通过判断target是否在有序区间内从而缩小范围。感觉有点低估二分法了，能变形好多解法啊！！

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

我的题解

如果左区间有序，移动右指针，如果右区间有序移动左指针，直到两个指针相遇。写得好乱...

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

官方题解

一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。

我们考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。

在二分查找的每一步中，左边界为 low，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较，可能会有以下的三种情况：

第一种情况是 nums[pivot]<nums[high]。如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

第二种情况是 nums[pivot]>nums[high]。如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot 就不会与 high 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]=nums[high] 的情况。

当二分查找结束时，我们就得到了最小值所在的位置。

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

心得

自己写得真是乱七八糟，官解就优雅很多。当右边比较大的时候说明右区间有序，最小值在左区间，收窄右区间（中间值有可能最小，故不越界），否则说明右区间无序，最小值在右区间，收窄左区间（中间值不可能为最小，故越界）。另外由于中间值是向下取整且循环条件是小于，故不可能等于右指针，所以无需考虑中间值=右边的情况。

二分的思想在于每次淘汰一半！！