首页 > 代码库 > [LeetCode] Search in Rotated Sorted Array [35]

[LeetCode] Search in Rotated Sorted Array [35]

题目

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

原题链接(点我)

解题思路

旋转数组中的查找。[1, 2, 3, 4, 5, 6]的一个旋转数组为[4, 5, 6, 1, 2, 3]。在旋转数组中寻找一个数。
最直接的方法,一次遍历,时间复杂度O(n)。但是既然是一个部分有序的数组,那么对于有序的部分我们可以想方法用二分查找。这个可以提高效率。

代码实现

class Solution {
public:
    int search(int A[], int n, int target) {
        if(A==NULL || n<=0) return -1;
        int begin = 0, end = n-1;
        while(begin<=end){
            int mid = begin + (end-begin)/2;
            if(A[mid] == target)
                return mid;
            if(A[mid] > A[end]){
                //前半段
                if(A[begin]<=target && A[mid] > target){
                    //target 在 begin 和 mid-1 之间
                    end = mid-1;
                }else{
                    begin = mid+1;
                }
            }else if(A[mid] < A[end]){
                //在后半段
                if(A[mid] < target && A[end] >=target){
                    //target 在 mid+1 和 end 之间
                    begin = mid+1;
                }else{
                    end = mid-1;
                }
            }else{                // 因为这个题数组中不含有重复元素,此时begin==end==mid并且A[mid]!=target,所以不存在                break;
            }
        }
        return -1;
    }
};

如果你觉得本篇对你有收获,请帮顶。
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你可以搜索公众号:swalge 或者扫描下方二维码关注我

(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/30471141 )