漫画：“旋转数组”中的二分查找
The following article is from 程序员小灰 Author 小灰
脚本之家
你与百万开发者在一起
作者：小灰
来源：程序员小灰
上周，小灰分享了最最基础的二分查找算法，没看过的小伙伴可以点击下面链接：
文章的最后，小灰遗留了一个问题：
在一个旋转有序数组中，如何查找一个整数呢？
注意这里有一个前提：我们并不直接知道给定数组的旋转点。
如何解决呢？今天让我们来做详细介绍：
是哪三种结果呢？我们仍然以数组【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-
●
返回 上一级 搜索“Java 女程序员 大数据 留言送书 运维 算法 Chrome 黑客 Python JavaScript 人工智能 女朋友 MySQL 书籍 等关键词获取相关文章推荐。