二分法——二分查找的变种
#0
这篇文章将谈一谈二分查找的几个变种问题。
首先回顾下前文提到的运用二分查找时对线性容器的要求：
-
这个线性容器中的元素是有序的 -
这个线性容器中不存在重复的元素
本文将会涉及两种情况：
-
当线性容器中存在重复元素并且元素保持有序时 -
当线性容器中元素不保持有序并且不存在重复元素时
#1
同样是在线性容器中寻找目标值target，当线性容器中存在重复元素并且元素保持有序时，问题变成了找到「第一个等于target的元素」和「最后一个等于target的元素」。
以nums代表「线性容器」，以left和right代表「两个指针」，target表示「查找的目标值」
No.34
这道题就是在排序数组中查找元素的「第一个位置」和「最后一个位置」，假设数组默认是升序的。这道题的解法可以在二分查找的基础上演化出来，而只需要针对出现重复元素做特殊处理。
以下是参考思路
-
确定两个指针指向元素的含义(不变) -
确定两个指针移动与停止的条件(不变) -
确定指针移动时的step(不变) -
确定指针移动时的额外执行逻辑 -
计算mid，mid代表查找范围的中点
-
当nums[mid] < target时 -
处理方式不变
-
当nums[mid] > target时 -
处理方式不变
-
当nums[mid] == target时 -
处理方式发生变化
在原有二分查找的思路基础上，只有当「nums[mid] == target」时会有「额外的处理」，这里的处理方式在查找第一个元素位置和最后一个元素位置时有不同的处理方式。
实现的代码请参考
class Solution {
public int[] searchRange(int[] nums, int target) {
int len = nums.length;
int left = 0,right = len - 1;
int resLeft = -1,resRight = -1;
while(left < right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
// nums[mid] == target
// 这里是在寻找第一个元素位置时的处理方式
if(mid == 0 || nums[mid - 1] != target) resLeft = mid;
// 当没有找到第一个元素时，移动right指针
right = mid - 1;
}
}
left = 0;
right = len - 1;
while(left < right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
// nums[mid] == target
// 这里是在寻找最后一个元素位置时的处理方式
if(mid == 0 || nums[mid + 1] != target) resRight = mid;
// 当没有找到最后一个元素时，移动left指针
left = mid + 1;
}
}
return new int[] {resLeft,resRight};
}
}
结合动图更容易理解在nums[mid] == target，却又没有找到第一个或最后一个目标值时缩小查找范围的处理方式。
#10
接下来是二分法的另外一个变种，线性容器中元素不保持有序并且不存在重复元素，但是这个条件中「元素不保持有序」并不是意味着元素就是杂乱无序。以33.搜索旋转排序数组为例，原本有序的数组在某个点上进行了旋转。旋转的结果是整体上的元素不保持有序，但是局部保持有序。
No.33
具体题目的描述请登录LeetCode网站查看。
由于原本有序的数组在某个点上进行了旋转，因此数组只能在「局部保持元素有序」。利用数组在局部保持的元素有序性，同样可以运用二分法查找目标元素。
按照题目要求，旋转后的数组可以抽象成这样。
那么在进行二分查找的时候，根据「mid可能出现的位置」会出现四种情况，分别是
后两种是退化情况，暂时不纳入考虑。因此这里只需要处理前两种情况。
每种情况存在两种缩小查找范围的方向，前两种一共是四个方向，如图所示。
「二分法的核心是减少查找的范围」，减少查找的范围是通过移动left指针和right指针执行的。那么在进行指针移动前，需要进行两步判断。这两步判断也是双指针解题套路四步中的第四步——「确定指针移动时的额外执行逻辑」
-
如果nums[mid] > nums[left]，那么处于情况一 -
target在mid左侧 -
target < nums[mid] && nums[left] < target -
target在mid右侧 -
如果nums[mid] < nums[left]，那么处于情况二 -
target在mid左侧 -
target > nums[mid] && nums[right] > target -
target在mid右侧
同样也需要考虑到「边界条件」，这里的边界条件是当target出现在这四个点上。
这么分析后，相信你应该对题目的解法有了眉目。为了更好地体现思路，这里使用递归的方式实现二分查找。当然考虑到退化情况和边界条件需要对代码进行调整，具体细节请参考代码实现。
class Solution {
public int search(int[] nums, int target) {
int left = 0,right = nums.length - 1;
if(nums.length == 0) return -1;
return binarySearch(nums,left,right,target);
}
private int binarySearch(int[] nums,int left,int right,int target) {
// 虽然这里看上去使得退出条件发生了变化
// 但是实际上在return时，left == right
// 二分查找的退出条件依然是left <= right
if(left < right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] == target) return mid;
// 这里nums[mid] == nums[left]是为了对应数组只有两个元素的情况
if(nums[mid] >= nums[left]) {
// 退化情况会在这里进行处理
// 退化情况下nums[left] <= target始终满足
// 因此由target与nums[mid]大小决定如何减小查找范围
// 这里nums[left] == target是对应边界条件
if(target < nums[mid] && nums[left] <= target) return binarySearch(nums,left,mid - 1,target);
return binarySearch(nums,mid + 1,right,target);
} else {
// 同样这里nums[right] == target是为了对应边界条件
if(target > nums[mid] && nums[right] >= target) return binarySearch(nums,mid + 1,right,target);
return binarySearch(nums,left,mid - 1,target);
}
}
return nums[left] == target ? left : -1;
}
}
由于数组在某一点发生了旋转，因此left指针和right指针分布在两侧是最常见的情况(指情况一和情况二)，进而需要考虑到两个指针在同一侧，最后考虑到边界条件，使得代码中的条件判断能够覆盖所有的情况。
#11
本文介绍了二分法的两个变种问题，分别是「当线性容器中存在重复元素并且元素保持有序时目标值的查找」和「当线性容器中元素不保持有序并且不存在重复元素时目标值的查找」。下一篇将会继续讨论二分法的变种问题，「当线性容器存在重复元素并不保持有序时目标值的查找」，这对应第一篇文章中二分查找对线性容器的「两种要求同时打破」。