描述

一个无重复元素的有序数组，在某一个位置进行了旋转，给定一个值，查找是否在数组中，如果存在则返回此元素的位置，否则返回-1。

输入

数组：[4, 5, 6, 7, 0, 1, 2, 3]，元素： 5，

输出

1

分析

提到在有序数组中进行查找一定会用到二分查找，二分查找的核心是确定左右边界的移动规则。在一个有序数组中，目标值大于中间值则左边界移动到中间位置，否则右边界移动到中间位置，以此每次排除掉一半元素。

当有序数组在某个元素处进行翻转后则将一个有序数组分割成了两部分的有序排列。

旋转排序数组示意图

参考上图，pivot为旋转点，则:

1，[first, pivot]为有序数组；

2，[pivot+1, last]为有序数组；

在取中间值mid后，若 A[mid] == target，则查找成功，否则继续分析mid和pivot的关系：

1，mid <= pivot；

2，mid > pivot；

对于mid<=pivot，如下图：

mid<pivot示意图
则[first, mid]为有序数组，有：

A[first] <= A[mid]

如果，目标值（target）在first和mid之间，则有如下等式成立：

A[first]<=target && target<A[mid]

在此情况下，移动last至mid：

last = mid;

如果目标值不在[first, mid]范围，则移动first至mid+1处：

first = mid + 1;

对于mid > pivot，如下图

mid>pivot示意图

则有：

A[first] > A[mid]

此时[mid, last]为有序数组，若target是否在有序数组内，则有以下判断成立：

A[mid]<target && target<=A[last]

在此情况下，移动first至mid下一个位置：

first = mid + 1;

若，target在[mid, last]之外，则移动last至mid：

last = mid;

以上为左右边界移动逻辑的分析，根据以上分析很容易写出响应的代码。

实现

int SearchInRotatedSortedArray(int A[], int len, int target)
{
    int first = 0;
    int last = len;
    
    while (first != last) {
        int mid = (first + last) / 2;
        if (A[mid] == target) {
            return mid;
        }
        
        // first和mid是一个连续的排序区间段
        if (A[first] <= A[mid]) {
            // target在first和mid的区间段，移动last
            if (A[first]<=target && target<A[mid]) {
                last = mid;
            } else {
                first = mid + 1;
            }
        }
        else {
            // mid和last是一个连续的排序区间段
            if (A[mid]<target && target<=A[last-1]) {
                // 移动first
                first = mid + 1;
            } else {
                last = mid;
            }
        }
    }
    
    return -1;
}

不难看出，以上算法的时间复杂度为O(logn)，空间复杂度为O(1)。

再深入一步

如果在旋转后的有序数组中存在重复元素我们又该如何做呢？

分析

在有重复元素存在的情况下：

A[first] <= A[mid]时无法判断[first, mid]为一个有序数列，需要拆分为两部分了：

1，A[first] < A[mid]，则[first, mid]为有序数列；

2，A[first] == A[mid]，确定不了[first, mid]是否为有序，那就first++，往前移动一步再进行判断。

实现

int searchInRotatedSortedArrayWithDuplicate(int A[], int len, int target)
{
    int first = 0;
    int last = len;
    
    while (first != last) {
        int mid = (first + last) / 2;
        if (A[mid] == target) {
            return mid;
        }
        if (A[first] < A[mid]) {
            // first到mid之间是一个连续的排序区间段
            if (A[first]<=target && target<A[mid]) {
                // target在first和mid之间，移动Last
                last = mid;
            } else {
                first = mid + 1;
            }
        }
        else if(A[first] > A[mid]) {
            // mid到last之间是一个连续的排序区间段
            if (A[mid]<target && target<=A[last-1]) {
                //target在mid和last之间,移动first
                first = mid + 1;
            } else {
                last = mid;
            }
        }
        else {
            // first和mid相等，移动first
            ++first;
        }
    }
    
    return -1;
}

在存在重复元素的情况下，算法的时间复杂度为O(n)，空间复杂度为O(1)。

---

代码在这儿