漫画：“旋转数组”中的二分查找

上周一，小灰分享了最最基础的二分查找算法，没看过的小伙伴可以点击下面链接：

漫画：什么是二分查找？（修订版）

文章的最后，小灰遗留了一个问题：

在一个旋转有序数组中，如何查找一个整数呢？

注意这里有一个前提：我们并不直接知道给定数组的旋转点。

如何解决呢？今天让我们来做详细介绍：

是哪三种结果呢？我们仍然以数组【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—————

最后安利一下小灰创建的免费知识星球，

每天都有许多有趣的抢答活动和各种奖品，

关键是不要钱！欢迎大家扫码加入：

给个[在看]，是对小灰莫大的支持！