在旋转有序数组内找特定的值-白红宇

要求

给定一没有重复元素的旋转数组（它对应的原数组是有序的），求给定元素在旋转数组内的下标（不存在的返回-1）。

例如

有序数组为｛0，1，2，4，5，6，7｝，它的一个旋转数组为｛4，5，6，7，0，1，2｝。

元素6在旋转数组内，返回2

元素3不在旋转数组内，返回-1

分析

遍历一遍，可以轻松搞定，时间复杂度为O(n)，因为是有序数组旋转得到，这样做肯定不是最优解。有序，本能反映用二分查找，举个例子看看特点

可以看出中间位置两段起码有一个是有序的（不是左边，就是右边），那么就可以在有序的范围内使用二分查找；如果不再有序范围内，就到另一半去找。

参考代码

int search(int A[], int n, int target) {        int beg = 0;        int end = n - 1;        while (beg <= end)        {            int mid = beg + (end - beg) / 2;            if(A[mid] == target)                return mid;            if(A[beg]  <= A[mid])            {                if(A[beg] <= target && target < A[mid])                    end = mid - 1;                else                     beg = mid + 1;            }            else            {                if(A[mid] < target && target <= A[end])                    beg = mid + 1;                else                    end = mid - 1;            }        }        return -1;    }

扩展

上边的有求是没有重复的元素，现在稍微扩展下，可以有重复的元素，其他的要求不变。

思路

大致思路与原来相同，这是需要比较A[beg] 与　A[mid]的关系

A[beg] <　A[mid] ————左边有序

A[beg] >　A[mid] ————右边有序

A[beg] =　A[mid] ————++beg

bool search(int A[], int n, int target) {        int beg = 0;        int end = n - 1;        while (beg <= end)        {            int mid = beg + (end - beg) / 2;            if(A[mid] == target)                 return true;            if(A[beg] < A[mid])            {                if(A[beg] <= target && target < A[mid])                    end = mid - 1;                else                    beg = mid + 1;            }            else if(A[beg] > A[mid])            {                if(A[mid] < target && target <= A[end])                    beg = mid + 1;                else                    end = mid - 1;            }            else                ++beg;        }        return false;    }

本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3687583.html，如需转载请自行联系原作者