文章目录
前言
??????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}。 可以采用向上取整来解决该问题，如下：
public int search(int[] nums) {
int start=0,end=nums.length-1,mid=0;
while(start<end){
mid=(start+end)/2+1;
if(nums[mid]>=nums[0])
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[n-1] 的关系来得到算法思路，和求最大值类似，不做详述，代码参考如下：
public int search(int[] nums) {
int start=0,end=nums.length-1,mid=0;
while(start<end){
mid=(start+end)/2;
if(nums[mid]>nums[nums.length-1])
start=mid+1;
else
end=mid;
}
return start;
}
三、标准二分查找算法
??????在不含重复元素的升序数组 arr 中查找 t，如果存在：返回 t 的下标，不存在返回 -1。代码如下：
public 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 应该插入的下标。代码如下：
public 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 如下：
public 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;
}
int res=-1;
for(int i=start;i<arr.length&&arr[i]<=t;i++){
if(arr[i]==t){
res=i;
break;
}
}
return res;
}
??????采用 start < end，假设 t 存在，且第一次出现的下标为 f ，那么最终得到的 start 值为 f 或 f-1；如果 t 不存在，start 为 t 的插入位置。
??????示例：在下面几个数组中查找 4 第一次出现的位置，在循环结束时，start 的值如下：
??????数组1：2 4 4 5 ?????? start值：0
??????数组2：2 4 4 5 5?????start值：1
??????数组1：2 3 3 5 ?????? start值：3
代码 2 如下：
public 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;
}
if(start<nums.length&&arr[start]==t)
return start;
return -1;
}
??????采用 start <= end，假设 t 存在，那么最终得到的 start 值即为返回值；如果 t 不存在，start 为 t 的插入位置(这里注意边界条件：start 可能为 arr.length)。
??????示例：在下面几个数组中查找 4 第一次出现的位置，在循环结束时，start 的值如下：
??????数组1：2 4 4 5 ?????? start值：1
??????数组2：2 4 4 5 5?????start值：1
??????数组1：2 3 3 5 ?????? start值：3
??????总体上看，代码 2 更加简洁一些。
一、在排序数组中查找元素的第一个和最后一个位置
??????题目链接：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 ：
//在一些语言中，位运算的优先级较低，需要注意运算顺序。
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 ：
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;
}
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)。代码参考如下：
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,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};
}
二、搜索旋转排序数组
??????题目链接：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)。
public 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)。参考代码如下：
public 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+1;
if(nums[mid]>=nums[0])
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 的位置来采用不同的缩小区间方向。参考代码如下：
public 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
??????这道题比较简单。执行两次二分查找即可，下面的算法先求目标值所在行，然后在该行中判断目标值所在的位置。参考算法如下：
public 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（推荐）
??????可以通过将二维数组看作为一个升序的一维数组，然后执行二分查找，这个思路比较清奇，也很好实现。稍有点麻烦的地方在于将二维坐标转换为一位坐标。参考代码如下：
public 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
??????这个问题可以通过 前言 中 二、求旋转数组中的最小值下标 直接得到结果，如下所示：
public int findMin(int[] nums) {
int start=0,end=nums.length-1,mid=0;
while(start<end){
mid=(start+end)/2;
if(nums[mid]>nums[nums.length-1])
start=mid+1;
else
end=mid;
}
return nums[start];
}
思路 2
??????这个代码稍有点复杂，仅作为参考，用来理解二分查找中的边界条件（特殊情况）处理，它采用的是和 nums[0] 来做比较。参考代码如下：
public 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/
public 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 就不一样了。
总结
??????完
