文章目录
- 前
- 示例
- 一、求旋转数组中的最大值下标
- 二、求旋转数组中的最小值下标
- 三、标准二分查找算法
- 变体1：查找待插入的位置
- 变体2：查找第一次出现的位置
- 代码 1 如下：
- 一、在排序数组中查找元素的第一个和最后一个位置
- 思路1
- 思路2 O(logn)
- 思路3 O(logn) 建议使用
- 二、搜索旋转排序数组
- 思路1
- 思路2
- 思路3
- 三、搜索二维矩阵
- 思路 1
- 思路 2（推荐）
- 四、寻找旋转排序数组中的最小值
- 思路 1
- 思路 2
- 五、寻找峰值
- 思路
- 总结
前
Leetcode算法系列：https://leetcode.cn/study-plan/algorithms/?progress=te66302
二分查找续。
二分法的本质不是单纯指从有序数组中快速找某个数，这只是二分法的一个应用，而是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用二分法来缩小规模，逐渐求解。
示例
一、求旋转数组中的最大值下标
求旋转数组中的最大值（不含重复元素，也是它的一个分界点，旋转数组的定义见下方的算法题2：搜索旋转数组）的下标：
在这里原数组应该如何二分呢？数组经旋转后，分为两个升序子数组，这里即求左子数组中最后一个元素的下标（这里应当考虑旋转数组旋转个数 k 为 0 的情况，此时旋转数组等同于原数组）。
那么在每次二分时，可以判断nums[mid] 和 nums[0] 的大小关系，如果 nums[mid] > =nums[0]，那么最终结果可能会由 mid 给出，故令 start=mid；否则，最终结果不可能由 mid 给出，并且最终结果在 mid 的左侧（即左子数组中）,令 end=mid-1。
而令 start=mid 在一般情况是不妥的，由于对 mid 的计算默认采用的是向下取整，在某些情况下会造成死循环。比如数组 {6，7}。 可以采用向上取整来解决该问题，如下：
1
2
3
4
5
6
7
8
9
10
11
12
13public int search(int[] nums) { int start=0,end=nums.length-1,mid=0; while(start<end){ //mid=(start+end)/2+1; //错误！！ mid=(start+end+1)/2; // 使用此方式，做到向上取整。 if(nums[mid]>=nums[start]) start=mid; else end=mid-1; } return start; }
一些概念：
不稳定收缩：会有 start=mid 或者 end=mid 出现（缩小数据规模时在区间边界有不确定性出现），此时的循环条件通常采用 < ，最终结果通常在循环结束后由 start 或 end 给出；
稳定收缩：即 start =mid+1 和 end =mid-1 一起出现（即在缩小数据规模时在区间边界有着清晰的决策），循环条件通常采用 <= ，最终结果可在循环内给出，也可在循环结束后由 start 和 end 给出；
在不稳定收缩中：向下取整不能和 start =mid 同时出现，向上取整不能和 end=mid 同时出现。
二、求旋转数组中的最小值下标
类似的，我们也可以求得旋转数组的最小值，此时通过向下取整和与 nums[end] 的关系来得到算法思路，和求最大值类似，不做详述，代码参考如下：
1
2
3
4
5
6
7
8
9
10
11
12public int search(int[] nums) { int start=0,end=nums.length-1,mid=0; while(start<end){ mid=(start+end)/2; if(nums[mid]>nums[end]) start=mid+1; else end=mid; } return start; }
三、标准二分查找算法
在不含重复元素的升序数组 arr 中查找 t，如果存在：返回 t 的下标，不存在返回 -1。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public int search(int[] arr, int t) { if(arr==null||arr.length==0) return -1; int start=0,end=arr.length-1,mid=0; while(start<=end){ mid=(start+end)/2; if(arr[mid]==t) return mid; if(arr[mid]>t) end=mid-1; else start=mid+1; } return -1; }
变体1：查找待插入的位置
在不含 t 的升序数组 arr 中查找 t 应该插入的位置，插入之后也应该保证数组升序，返回 t 应该插入的下标。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14public int search(int[] arr, int t) { if(arr==null||arr.length==0) return -1; int start=0,end=arr.length-1,mid=0; while(start<=end){ mid=(start+end)/2; if(arr[mid]>t) end=mid-1; else start=mid+1; } return start; }
start 为返回结果。
变体2：查找第一次出现的位置
在含重复元素的升序数组 arr 中查找 t 出现的第一次位置，如果存在：返回 t 的下标，不存在返回 -1。
代码 1 如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14public int search(int[] arr, int t) { if(arr==null||arr.length==0) return -1; int start=0,end=arr.length-1,mid=0; while(start<end){ mid=(start+end)/2; if(arr[mid]>=t) end=mid; else start=mid+1; } return arr[start]==t?start:-1; }
一、在排序数组中查找元素的第一个和最后一个位置
题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
题目描述：
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
思路1
找到目标值在数组中出现的开始位置，然后从开始位置开始遍历数组得到结束位置。
时间复杂度为O(logn)+O(m)，m为目标值在数组中的个数。
采用 start < end ：
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//在一些语言中，位运算的优先级较低，需要注意运算顺序。 public int[] searchRange(int[] nums, int target) { if(nums==null||nums.length==0) return new int[]{-1,-1}; int start=0,end=nums.length-1; int mid=0; while(start<end){ mid=(start+end)/2; if(nums[mid]>=target) end=mid-1; else start=mid+1; } //假设 target 第一次出现的下标为 f，那么在此处，start 等于 end，其值为 f 或 f-1 int s=-1,e=-1; //确定 s 的值 for(int i=start;i<nums.length&&nums[i]<=target;i++){ if(nums[i]==target){ s=i; break; } } //边界条件：此数组中不存在 target if(s==-1) return new int[]{-1,-1}; //确定 e 的值 for(int i=s;i<nums.length&&nums[i]==target;i++) e=i; return new int[]{s,e}; }
采用 start <= end ：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public int[] searchRange(int[] nums, int target) { if(nums==null||nums.length==0) return new int[]{-1,-1}; int start=0,end=nums.length-1; int mid=0; while(start<=end){ mid=(start+end)/2; if(nums[mid]>=target) end=mid-1; else start=mid+1; } if(start==nums.length||nums[start]!=target) return new int[]{-1,-1}; //确定 end 的值 for(int i=start;i<nums.length&&nums[i]==target;i++) end=i; return new int[]{start,end}; }
思路2 O(logn)
分别找到目标值在数组中出现的开始位置和结束位置。
时间复杂度为O(logn)。代码参考如下：
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
28public int[] searchRange(int[] nums, int target) { if(nums==null||nums.length==0) return new int[]{-1,-1}; int start=0,end=nums.length-1,mid=0; while(start<=end){ mid=(start+end)/2; if(nums[mid]>=target) end=mid-1; else start=mid+1; } if(start==nums.length||nums[start]!=target) return new int[]{-1,-1}; int s=start; //用 s 存储开始位置。 start=0; end=nums.length-1; while(start<=end){ mid=(start+end)/2; if(nums[mid]>target) end=mid-1; else start=mid+1; } return new int[]{s,end}; }
思路3 O(logn) 建议使用
分别找到目标值在数组中出现的开始位置和结束位置。
时间复杂度为O(logn)。代码参考如下：
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
30public int[] searchRange(int[] nums, int target) { if(nums==null||nums.length==0) return new int[]{-1,-1}; int start=0,end=nums.length-1,mid=0; while(start<end){ mid=(start+end)/2; if(nums[mid]<target) start=mid+1; else end=mid; } if(nums[start]!=target) return new int[]{-1,-1}; int[] res=new int[2]; res[0]=start; start=0; end=nums.length-1; while(start<end){ mid=(start+end+1)/2; if(nums[mid]>target) end=mid-1; else start=mid; } res[1]=start; return res; }
二、搜索旋转排序数组
题目链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/
题目描述：整数数组 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 。
思路1
简单的，通过遍历找到分界点，然后针对每一部分采用二分查找，时间复杂度O(logn)+O(n)。
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
26public int search(int[] nums, int target) { int k=0,len=nums.length-1; for(int i=1;i<=len&&nums[i]>nums[i-1];i++){ k=i; } //此时 k 为第一段末尾元素的下标 if(target>=nums[0]) return s(nums,target,0,k); else return s(nums,target,k+1,len); } public int s(int[] nums,int target,int s,int e){ int mid=0; while(s<=e){ mid=(s+e)/2; if(nums[mid]==target) return mid; if(nums[mid]>target) e=mid-1; else s=mid+1; } return -1; }
思路2
在 1 的基础上通过二分查找分界点（在 前言 中的求最大值下标算法），然后再通过二分查找来查询目标值。由此时间复杂度为O(logn)。参考代码如下：
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
31public int search(int[] nums, int target) { int len=nums.length-1; int start=0,end=len,mid=0; while(start<end){//求分界点处最大值的下标 mid=(start+end+1)/2; if(nums[mid]>=nums[start]) start=mid; else end=mid-1; } if(target>=nums[0]) return s(nums,target,0,start); else return s(nums,target,start+1,len); } public int s(int[] nums,int target,int s,int e){ int mid=0; while(s<=e){ mid=(s+e)/2; if(nums[mid]==target) return mid; if(nums[mid]>target) e=mid-1; else s=mid+1; } return -1; }
思路3
基于上面两种思路，更进一步，能否采用一次二分查找直接在旋转数组中找到目标值呢？答案是可以的，无非通过多重判断来确定如何缩小数据规模（取左侧还是右侧），这样得到的算法更加清晰简洁，时间复杂度为O(logn) 。
在循环中，首先需要判断 target 和 nums[0] 的关系，得到 target 落在左子区间还是右子区间，据此：判断 nums[mid] 的所处位置（通过和 nums[0] 比较得到），根据 target 的位置来采用不同的缩小区间方向。参考代码如下：
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
35public int search(int[] nums, int target) { int len=nums.length-1; int start=0,end=len,mid=0; while(start<=end){ mid=(start+end)/2; if(target<nums[0]){ // 目标值坐落在右子区间 if(nums[mid]>=nums[0]) start=mid+1; else{ //这里执行标准二分查找 if(nums[mid]==target) return mid; if(nums[mid]>target) end=mid-1; else start=mid+1; } } else{//目标值坐落在左子区间 if(nums[mid]<nums[0]) end=mid-1; else{ if(nums[mid]==target) return mid; if(nums[mid]<target) start=mid+1; else end=mid-1; } } } return -1; }
三、搜索二维矩阵
题目链接：https://leetcode.cn/problems/search-a-2d-matrix/
题目描述：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
思路 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
33public boolean searchMatrix(int[][] matrix, int target) { int m=matrix.length,n=matrix[0].length; int start=0,end=m-1,mid=0; while(start<=end){ mid=(start+end)/2; if(matrix[mid][n-1]==target) return true; if(matrix[mid][n-1]>target) end=mid-1; else start=mid+1; } //在此处，由 start 给出数组中 target 的插入位置， 即目标值可能存在于由start表示的那行中。 if(start>m-1)//此处注意边界条件 start 的取值可能为 m。 return false; int locationInLow=start; start=0;end=n-1; while(start<=end){ mid=(start+end)/2; if(matrix[locationInLow][mid]==target) return true; if(matrix[locationInLow][mid]>target) end=mid-1; else start=mid+1; } return false; }
思路 2（推荐）
可以通过将二维数组看作为一个升序的一维数组，然后执行二分查找，这个思路比较清奇，也很好实现。稍有点麻烦的地方在于将二维坐标转换为一位坐标。参考代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public boolean searchMatrix(int[][] matrix, int target) { int m=matrix.length,n=matrix[0].length; int start=0,end=m*n-1,mid=0; while(start<=end){ mid=(start+end)/2; if(retValue(mid,n,matrix)==target) return true; if(retValue(mid,n,matrix)<target) start=mid+1; else end=mid-1; } return false; } //通过一维下标 index 得到在二维数组中相应的元素值 public int retValue(int index,int n,int[][] matrix){ return matrix[index/n][index%n]; }
四、寻找旋转排序数组中的最小值
题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
题目描述：
已知一个长度为 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
这个问题可以通过 前言 中 二、求旋转数组中的最小值下标 直接得到结果，如下所示：
1
2
3
4
5
6
7
8
9
10
11
12public int findMin(int[] nums) { int start=0,end=nums.length-1,mid=0; while(start<end){ mid=(start+end)/2; if(nums[mid]>nums[end]) start=mid+1; else end=mid; } return nums[start]; }
思路 2
这个代码稍有点复杂，仅作为参考，用来理解二分查找中的边界条件（特殊情况）处理，它采用的是和 nums[0] 来做比较。参考代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public int findMin(int[] nums) { int start=0,end=nums.length-1,mid=0; while(start<=end){ mid=(start+end)/2; if(nums[mid]>=nums[0]) start=mid+1; else{ //通过 nums[mid] 和 nums[mid-1] 之间的关系来选择取左区间还是已找到目标值 if(nums[mid]>nums[mid-1]) end=mid-1; else return nums[mid]; } } return nums[0]; //返回 nums[0] 对应于此时的旋转数组仍为升序数组的情况。 }
五、寻找峰值
题目链接：https://leetcode.cn/problems/find-peak-element/
题目描述：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
对于所有有效的 i 都有 nums[i] != nums[i + 1]
思路
由于题目保证了 nums[i]!=nums[i+1]，那么在二分时，将 nums[mid] 的值和 nums[mid+1] 作比较，假设 nums[mid] < nums[mid+1] ，此时必有峰值存在于 mid 右侧，确切的来说 mid+1 可能为峰值所在位置，而 mid 不可能为峰值所在位置，那么得到下一轮的区间为 [mid+1，end] 。
读者可参考题解：https://leetcode.cn/problems/find-peak-element/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-qva7v/
1
2
3
4
5
6
7
8
9
10
11
12
13public int findPeakElement(int[] nums) { int n = nums.length; int start=0,end=n-1,mid=0; while(start<end){ mid=(start+end)/2; if(nums[mid]<nums[mid+1]) start=mid+1; else end=mid; } return start; }
注意：由于采用了向下取整 且 循环条件为 start<end，那么在循环中 mid+1 绝对不会造成数组越界。而采用 start<= end 就不一样了。
总结
完
最后
以上就是阔达可乐最近收集整理的关于LeetCode算法题1：二分查找续前一、在排序数组中查找元素的第一个和最后一个位置二、搜索旋转排序数组三、搜索二维矩阵四、寻找旋转排序数组中的最小值五、寻找峰值总结的全部内容，更多相关LeetCode算法题1：二分查找续前一、在排序数组中查找元素内容请搜索靠谱客的其他文章。
发表评论 取消回复