上周一,小灰分享了最最基础的二分查找算法,没看过的小伙伴可以点击下面链接:
文章的最后,小灰遗留了一个问题:
在一个旋转有序数组中,如何查找一个整数呢?
注意这里有一个前提:我们并不直接知道给定数组的旋转点。
如何解决呢?今天让我们来做详细介绍:
是哪三种结果呢?我们仍然以数组【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—————