漫画算法：“旋转数组”中的二分查找
漫画算法教程持续更新中
跟程序员小灰学算法之Day7
作者 | 程序员小灰
昨天，请小灰分享了最最基础的二分查找算法，没看过的小伙伴可以点击下面链接：
文章的最后，小灰遗留了一个问题：
在一个旋转有序数组中，如何查找一个整数呢？
注意这里有一个前提：我们并不直接知道给定数组的旋转点。
如何解决呢？今天让我们来做详细介绍：
是哪三种结果呢？我们仍然以数组【2，5，7，9，12，14，20，26，30】为例来进行分析：
第一步，我们定位到数组的中位数：
第二步，比较中位数和待查找目标整数之间的大小关系，这时候会出现三种可能性：
1.如果中位数>目标整数，则新的查找区间收缩在【start, mid-1】
2.如果中位数<目标整数，则新的查找区间收缩在【mid+1，end】
3.如果中位数 == 目标整数，则查找成功
（注意：下面的分析会比较烧脑，一次看不明白的小伙伴们可以多看几遍。另外，本文的所有分析都是基于升序数组。）
在分析之前，首先明确一个概念：旋转点。
旋转点是什么呢？我们这里规定，假设旋转有序数组恢复为普通有序数组，位于普通有序数组第一个位置的元素，就是旋转数组的旋转点。
直白地说，旋转点就是旋转数组中最小的元素：
那么，当我们选择中位数，进行一次二分查找的时候，会出现哪些结果呢？仅仅从中位数与旋转点的相对位置来看，有两种结果：
情况A，旋转点在中位数的右侧：
这种情况下有两个特点：
1.中位数以及它左侧的元素，全部是升序的。
2.最左侧元素，必定小于等于中位数。
情况B，旋转点在中位数的左侧，或与中位数重合：
这种情况下有两个特点：
1.中位数以及它右侧的元素，全部是升序的。
2.最左侧元素，必定大于中位数。
上面所分析的，仅仅是从中位数与旋转点的相对位置角度。如果再引入要查找的目标整数呢？上面的情况A和情况B，就会各自分为两种子情况。
首先回过头看看上述的情况A，要查找的目标整数（假设存在）有可能出现在哪里呢？
答案很简单：
1.查找目标在中位数的左侧
由于情况A的中位数左侧是升序区，所以查找目标出现在左侧的条件是：
最左侧元素 <= 查找目标 < 中位数
2.查找目标在中位数的右侧
由于查找目标出现在左侧的条件已经确定，那么出现在右侧的条件判断就简单了：
！（最左侧元素 <= 查找目标 < 中位数）
接下来我们再看看上述的情况B，要查找的目标整数（假设存在）可能出现在哪里呢？
答案也是同样道理：
1.查找目标在中位数的右侧
由于情况B的中位数右侧是升序区，所以查找目标出现在右侧的条件是：
中位数 < 查找目标 <= 最右侧元素
2.查找目标在中位数的左侧
由于查找目标出现在右侧的条件已经确定，那么出现在左侧的条件判断就简单了：
！（中位数 < 查找目标 <= 最右侧元素）
综上，我们总结了旋转数组二分查找可能出现的四种情况。
public static int rotatedBinarySearch(int[] array, int target){
int start = 0, end = array.length-1;
while(start<=end)
{
int mid = start + (end-start)/2;
if(array[mid]==target){
return mid;
}
//情况A：旋转点在中位数右侧
if(array[mid]>=array[start])
{
//最左侧元素 <= 查找目标 < 中位数
if(array[mid]>target && array[start]<=target){
end = mid - 1;
} else {
start = mid + 1;
}
}
//情况B：旋转点在中位数左侧，或与中位数重合
else {
//中位数 < 查找目标 <= 最右侧元素
if(array[mid]<target && target<=array[end]){
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] array = new int[]{9,10,11,12,13,1,3,4,5,8};
System.out.println(rotatedBinarySearch(array, 12));
}
—————END—————
世界总是奖励那些悄悄努力的人
给萌萌小灰点在看❤️