力扣解题思路：二分法 纠错记录

二分法

每次做题，只要看到题目要求说时间复杂度要不能大于O(logn)我就脑瓜子疼，因为一般这种情况就是需要用到二分法了，二分法的原理其实很简单，就是一次次的找数组中间的mid数，验证其是否满足要求，然后根据实际情况来移动low或者high。然而二分法最头疼的不在于他的原理，而在于他的边界条件的取值，例如while循环的条件中应该是l<h呢还是l<=h呢，以及当mid不满足条件后是h = mid还是h=mid+1还是l = mid还是l=mid+1呢？

其实判断这个也是有一定规律的，比如当mid不满足条件后是h = mid（因为mid可能是答案），那这时候while循环中的条件一般为l<h，因为如果此时l<=h的话会陷入一个死循环的状态，同样的道理，h=mid+1（l=mid-1）往往与l<=h配合使用，当然，具体情况应该具体分析，接下来我会列举几道使用二分法解题的例题。

另外，还有一个比较重要的点就是，我们写mid的时候要养成一个良好的习惯，不要使用mid = (h+l)/2,尽量使用mid = l + (h-l)>>2,这是因为l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。

先上一个比较简单的题目：

69. x 的平方根

思路：这一题题目没有给出时间复杂度的要求，所以我是用的暴力法哈哈：

public int mySqrt(int x) { long i = 0; long n = 0; while(n<=x){ i++; n = i*i; } return (int)i-1; }

接下来使用二分：一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。

if (x <= 1) { return x; } int l = 1, h = x; while (l <= h) { int mid = l + (h - l) >> 2; int sqrt = x / mid; if (sqrt == mid) { return mid; } else if (mid > sqrt) { h = mid - 1; } else { l = mid + 1; } }

二分法是写好了，那么我们是return h还是return l呢？不如我们举个例子：对于 x = 8，它的开方是 2.82842…，最后应该返回 2 而不是 3。在循环条件为 l <= h 并且循环退出时，h 总是比 l 小 1，也就是说 h = 2，l = 3，因此最后的返回值应该为 h 而不是 l。

744. 寻找比目标字母大的最小字母

思路：显然题目也没有做任何规定，暴力法也是可行的。这里我们还是主要看二分法：由题目，给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 个字符。

public char nextGreatestLetter(char[] letters, char target) { int l = 0, h = letters.length; while (l < h) { int m = l + (h - l) >> 2; if (letters[m] <= target) l = m + 1; else h = m; } return letters[l % letters.length]; }

一般情况下letters[l]是返回值，当目标字母比所有字母都大，需要返回letters[0]即letters[l % len]。

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

思路：我们只看二分法，若nums[m] <= nums[h]则旋转点在左边，可能就是mid,所以h = m，反之，旋转点在右边则l = m + 1，代码如下：

public int findMin(int[] nums) { int l = 0, h = nums.length - 1; while (l < h) { int m = l + (h - l) / 2; if (nums[m] <= nums[h]) { h = m; } else { l = m + 1; } } return nums[l]; }

因为退出循环时h = l，所以，此时return nums[h] 也是可以的，结果都是对的。

然后我试了一下和左边界相比较，发现有各种错误。。。我还是放弃了，以后记住一定要尽量和右边界比较！！！！！

但是其实用下面这一题的答案，左边界又是可以的！继续往后看：

public int findMin(int[] numbers) { int l = 0, r = numbers.length - 1; while (l < r) { if(numbers[l]<numbers[r]){ return numbers[l]; } int mid = ((r - l) >> 1) + l; //只要右边比中间大，那右边一定是有序数组 if (numbers[l] < numbers[mid]) { l = mid + 1; } else if (numbers[l] > numbers[mid]) { r = mid; //去重 } else l++; } return numbers[l]; }

剑指 Offer 11. 旋转数组的最小数字

思路：这一题和上一题基本一样，区别在于这一题是含有重复数字的！所以直接用上面的方法会导致错误。所以需要去重，比如[3,3,1,3]重复数字被换到两边会导致右边界判断无效！因为一定要和非重复数字比较才会时有意义的！所以我们移动右边界指针：

public int minArray(int[] numbers) { int l = 0, r = numbers.length - 1; while (l < r) { int mid = ((r - l) >> 1) + l; //只要右边比中间大，那右边一定是有序数组 if (numbers[r] > numbers[mid]) { r = mid; } else if (numbers[r] < numbers[mid]) { l = mid + 1; //去重 } else r--; } return numbers[l]; }

实际上也可以用左边界：

public int minArray(int[] numbers) { int l = 0, r = numbers.length - 1; while (l < r) { if(numbers[l]<numbers[r]){ return numbers[l]; } int mid = ((r - l) >> 1) + l; //只要右边比中间大，那右边一定是有序数组 if (numbers[l] < numbers[mid]) { l = mid + 1; } else if (numbers[l] > numbers[mid]) { r = mid; //去重 } else l++; } return numbers[l]; }

但是一定要注意;

if(numbers[l]<numbers[r]){ return numbers[l]; }

这句一定不可以掉！！因为有非逆序数组的测试用例！

33. 搜索旋转排序数组

思路：假设按照升序排序的数组在预先未知的某个点上进行了旋转。(例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2])搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。

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

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环。（可以用递归也可以用while循环）

public int search(int[] nums, int target) { return search(nums, 0, nums.length - 1, target); } private int search(int[] nums, int low, int high, int target) { if (low > high) return -1; int mid = (low + high) / 2; if (nums[mid] == target) return mid; if (nums[mid] < nums[high]) {//右边有序 if (nums[mid] < target && target <= nums[high])//右边有序时右边可以用范围判断 return search(nums, mid + 1, high, target); else return search(nums, low, mid - 1, target); } else {//左边有序 if (nums[low] <= target && target < nums[mid])//左边有序时左边可以用范围判断 return search(nums, low, mid - 1, target); else return search(nums, mid + 1, high, target); } } public int search(int[] nums, int target) { int len = nums.length; int left = 0, right = len-1; while(left <= right){ int mid = (left + right) / 2; if(nums[mid] == target) return mid; else if(nums[mid] < nums[right]){ if(nums[mid] < target && target <= nums[right]) left = mid+1; else right = mid-1; } else{ if(nums[left] <= target && target < nums[mid]) right = mid-1; else left = mid+1; } } return -1; }

81. 搜索旋转排序数组 II

思路：这一题和上一题是一样的，但是这一题中有重复数字，所以我们要增加一步去重的操作： 方法1：

public boolean search(int[] nums, int target) { int l = 0, r = nums.length-1; while(l<=r){ //处理重复数字 while(l<r&&nums[l]==nums[l+1]) ++l; while(l<r&&nums[r]==nums[r-1]) --r; int mid = l+(r-l)/2; if(nums[mid]==target) return true; //左半部分有序 if(nums[mid]>=nums[l]){ if(target<nums[mid]&&target>=nums[l]) r = mid-1;//target落在左半边 else l = mid+1; } else{//右半部分有序 if(target>nums[mid]&&target<=nums[r]) l = mid+1;//target落在右半边 else r = mid-1; } } return false; }

方法2：

public boolean search(int[] nums, int target) { int l = 0, r = nums.length-1; while(l<=r){ //处理重复数字 // while(l<r&&nums[l]==nums[l+1]) ++l; // while(l<r&&nums[r]==nums[r-1]) --r; int mid = l+(r-l)/2; if(nums[mid]==target) return true; if (nums[l] == nums[mid]) { l++;//l++;这句代码就代表着，这并非是真的二分查找 continue; } //左半部分有序 if(nums[mid]>=nums[l]){ if(target<nums[mid]&&target>=nums[l]) r = mid-1;//target落在左半边 else l = mid+1; } else{//右半部分有序 if(target>nums[mid]&&target<=nums[r]) l = mid+1;//target落在右半边 else r = mid-1; } } return false; }

类似的也有这两题：

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

思路：假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。请找出其中最小的元素。

public int findMin(int[] nums) { int l = 0, h = nums.length - 1; while (l < h) { int m = l + (h - l) / 2; if (nums[m] <= nums[h]) {//等于可加可不加 h = m; } else { l = m + 1; } } return nums[h];//可以是l }

当有重复元素时应该去重：

public int findMin(int[] nums) { /** 和 I 的做法类似, 都是二分法, 每次进入无序的那部分找出最小值 但是由于有重复值的情况, 需要加入 mid 元素等于 hi 元素的情况 此时应该将 hi 减 1 防止重复数字是最小元素 **/ int lo = 0, hi = nums.length-1; while(lo < hi) { int mid = lo+(hi-lo)/2; if(nums[mid] > nums[hi]) lo = mid+1; else if(nums[mid] < nums[hi]) hi = mid; else hi--;//去重 } return nums[lo]; }

当然也可以这样：

public int findMin(int[] nums) { int lo = 0, hi = nums.length-1; while(lo < hi) { while(lo<hi&&nums[lo]==nums[lo+1]) ++lo; while(lo<hi&&nums[hi]==nums[hi-1]) --hi; int mid = lo+(hi-lo)/2; if(nums[mid] > nums[hi]) lo = mid+1; else if(nums[mid] < nums[hi]) hi = mid; else hi--; } return nums[lo]; }

1095. 山脉数组中查找目标值

思路：

显然题目的要求是使用二分法，暴力法被禁止，类似于旋转数组，只需判断mid和mid+1的大小即可：

//>>> : 无符号右移，忽略符号位，空位都以0补齐 class Solution { public int findInMountainArray(int target, MountainArray A) { int peek = findPeek(A); int ans = binSearch1(A,0,peek,target); return ans>=0?ans:binSearch2(A,peek,A.length()-1,target); } //左边升序区间查找 int binSearch1(MountainArray A,int l,int rr,int t) { int r = rr; while(l<r) { int m = (l+r)>>>1; if(A.get(m)<t) l = m+1; else r = m; } return l<rr&&A.get(l)==t?l:-1; } // int binSearch1(MountainArray A,int l,int rr,int t) { // int r = rr; // while(l<=r) { // int m = (l+r)>>>1; // if(A.get(m) == t) return m;//也可以 // if(A.get(m)<t) // l = m+1; // else // r = m-1; // } // return l<rr&&A.get(l)==t?l:-1; // } //右边降序区间查找 int binSearch2(MountainArray A,int l,int rr,int t) { int r = rr; while(l<r) { int m = (l+r)>>>1; if(A.get(m)>t) l = m+1; else r = m; } return l<rr&&A.get(l)==t?l:-1; } //查找峰 int findPeek(MountainArray A) { int l = 0,r = A.length()-1; while(l<r) { int m = (l+r)>>>1; if(m+1<A.length()&&A.get(m)<A.get(m+1)) l = m+1; else r = m; } return l; } // int findPeek(MountainArray A) { // int l = 0,r = A.length()-1; // while(l<r) { // int m = (l+r)>>>1; // if(m+1<A.length()&&A.get(m)>A.get(m+1))//也可以 // r = m; // else // l = m+1; // } // return l; // } }

540. 有序数组中的单一元素

思路：一个有序数组只有一个数不出现两次，找出这个数。要求以 O(logN) 时间复杂度进行求解，因此不能遍历数组并进行异或操作来求解，这么做的时间复杂度为 O(N)。

Input: [1, 1, 2, 3, 3, 4, 4, 8, 8] Output: 2

这里提供两种思路的二分法。首先我们知道二分法移动左右边界的条件是目标数出现的位置，那么如何通过mid来判断目标数出现的位置呢？-> 因为除了目标数，其他所有的数都出现次数为2，也就是整个数组一定是奇数。如果 mid 和左边相等，我们就判断 (mid-left)%2 是否为 0，为 0 则说明左边的存在答案值，改变 right 的值；若不为 0 则说明右边的存在答案值，改变 left 的值。如果 mid 和右边相等也是同样的道理，但是一定要注意边界！！其实画个图就可以很清晰的辨认那些边界以避免出错。如果 mid 和左右都不相等，那这就是答案了。完整代码如下，注释也写得比较清晰：

public int singleNonDuplicate(int[] nums) { int left=0; int right=nums.length-1; while(left<right){ int mid=left+(right-left)/2; if(nums[mid] == nums[mid-1]){//中点跟左边的相等，则判断除开中点，左边还剩几位数； if((mid-left)%2 == 0){//若为偶数，则说明左边的存在答案值，改变right的值 right = mid-2; } else {//若为奇数，则说明右边的存在答案值，改变left的值 left = mid+1; } } else if(nums[mid] == nums[mid+1]){//中点跟右边的相等，则判断除开中点，右边还剩几位数； if((right-mid)%2 == 0){//若为偶数，则说明右边的存在答案值，改变left的值 left = mid+2; } else {//若为奇数，则说明左边的存在答案值，改变right的值 right = mid-1; } } else{//中点跟左右都不相等，直接返回 return nums[mid]; } } return nums[left]; }

对于上面的方法，我个人觉得还是比较复杂的，接下来介绍一个稍微简单一点的思路，我们不用每次判断 mid 是和左边相等还是右边相等，只需要让 mid 每次位于偶数位然后每次判断 mid 和右边的数是否相等即可，如果不相等则目标数一定出现在了左边，否则在右边。那么我们如何保证 mid 每次都在偶数位上呢？->判断一下接可以啦(●ˇ∀ˇ●)，如果不在偶数位就将该数减一就可以了~~ 完整代码如下：

public int singleNonDuplicate(int[] nums) { int l = 0, h = nums.length - 1; while (l < h) { int m = l + (h - l) / 2; if (m % 2 == 1) { m--; // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数 } if (nums[m] == nums[m + 1]) { l = m + 2; } else { h = m; } } return nums[l]; }

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

思路：给定一个有序数组 nums 和一个目标 target，要求找到 target 在 nums 中的第一个位置和最后一个位置。

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

可以用二分查找找出第一个位置和最后一个位置，但是寻找的方法有所不同，需要实现两个二分查找。我们将寻找 target 最后一个位置，转换成寻找 target+1 第一个位置，再往前移动一个位置。这样我们只需要实现一个二分查找代码即可。

public int[] searchRange(int[] nums, int target) { int first = findFirst(nums, target); int last = findFirst(nums, target + 1) - 1; if (first == nums.length || nums[first] != target) { return new int[]{-1, -1}; } else { return new int[]{first, Math.max(first, last)}; } } private int findFirst(int[] nums, int target) { int l = 0, h = nums.length; // 注意 h 的初始值 while (l < h) { int m = l + (h - l) / 2; if (nums[m] >= target) { h = m; } else { l = m + 1; } } return l; }

注意，在寻找第一个位置的二分查找代码中，需要注意 h 的取值为 nums.length，而不是 nums.length - 1。先看以下示例：

nums = [2,2], target = 2

如果 h 的取值为 nums.length - 1，那么 last = findFirst(nums, target + 1) - 1 = 1 - 1 = 0。这是因为 findLeft 只会返回 [0, nums.length - 1] 范围的值，对于 findFirst([2,2], 3) ，我们希望返回 3 插入 nums 中的位置，也就是数组最后一个位置再往后一个位置，即 nums.length。所以我们需要将 h 取值为 nums.length，从而使得 findFirst返回的区间更大，能够覆盖 target 大于 nums 最后一个元素的情况。

再提供一个更简单的方法，但是可能比上一种慢一点，可以先找到目标数，然后往两边扩散即可，扩散过程的时间复杂度为O(n)：

public int[] searchRange(int[] nums, int target) { int left=0,right=nums.length-1; while (left<=right){ int mid = left + (right-left)/2; if(target>nums[mid]){ left=mid+1; }else if(target<nums[mid]){ right=mid-1; }else {//target==nums[mid] while (nums[left]!=target) left++; while (nums[right]!=target) right--; return new int[]{left,right}; } } return new int[]{-1,-1}; }

162. 寻找峰值

思路：峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。 数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

总的来说一句话：当前比右边小，那么肯定在右边会有峰顶，最差情况走到头，也是一个峰顶； 如果当前比左边小，那么肯定在左边会有峰顶，最差情况一路走到头，也是一个峰顶。

class Solution { // 题目已经要求相邻的数是不相等了 // 所以相邻的数只有两种情况： // nums[mid] > nums[mid + 1] 或 nums[mid] < nums[mid + 1] public int findPeakElement(int[] nums) { int left = 0; int right = nums.length - 1; while(left < right) { int mid = (left + right) / 2; if(nums[mid] > nums[mid + 1]) { // 左边高，说明左边有峰值，可能mid就是 right = mid; // mid在下一次查找中还要考虑在内 }else { left = mid + 1; // 右边高，说明在mid右边有峰值，所以mid一定不是 } // mid已经不是了，排除掉 } return left; } }