[leetcode] Search in Rotated Sorted Array 解题报告

问题描述

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.

思路一

从该数组中分离出两个升序序列,,然后根据条件判断应该对哪一个序列应用二分查找。
比如第二个升序序列的开始位置为index,如果target >= A[0],那么对[0 -> index-1]运用二分查找,否则对[index -> n-1]运用二分查找。

int find(int a[], int n)
    {
        if(n==0) return -1;
        if(n==1) return 0;
        if(n==2) return a[0]<=a[1]?0:1;
        int left=0,right=n-1, mid;
        while(right-left>1)
        {
            mid = left + (right-left)/2;
            if(a[left] < a[mid])
                left = mid;
            else
                right = mid;
        }
        if(a[left]>a[right])
            return right;
        else
            return 0;

    }
    int binarySearch(int a[], int left, int right, int target)
    {
        int mid;
        while(left<=right)
        {
            mid = left + ((right-left)>>1);
            if(a[mid] == target)
                return mid;
            else if(a[mid] < target)
                left = mid+1;
            else
                right = mid -1;
        }
        return -1;
    }
    int search(int A[], int n, int target) {
        //three steps: cut the array into two sorted arrays;
        //             search the target in two sorted arrays;
        //             return the index;
        int index = find(A,n);
        if(index == 0)
            return binarySearch(A,0,n-1,target);
        else
        {
            if(target >= A[0])
                return binarySearch(A,0,index-1,target);
            else
                return binarySearch(A,index,n-1,target);
        }
    }

思路二

直接对数组进行二分查找,[LeetCode] Search in Rotated Sorted Array II 解题报告
](http://fisherlei.blogspot.com/2013/01/leetcode-search-in-rotated-sorted-array_3.html).

int binarySearch(int a[], int left, int right, int target)
    {
        int mid;
        while(left<=right)
        {
            mid = left + ((right-left)>>1);
            if(a[mid] == target)
                return mid;
            if(a[left] <= a[mid])
            {
                if(a[mid]> target && a[left]<=target)
                    right = mid -1;
                else
                    left = mid +1;
            }
            else
            {
                if(a[mid]<target && a[right]>=target)
                    left = mid +1;
                else
                    right = mid -1;
            }
        }
        return -1;
    }
    int search(int a[], int n, int target) {
        return binarySearch(a,0,n-1,target);
    }