[leetcode]Search in Rotated Sorted Array II

tags: array, binary search, leetcode

问题描述

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

分析

和上一个问题的唯一不同点是,数组里面的元素可能是重复的。 为此需要剔除重复的元素。

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 if(a[left] > a[mid])
                right = mid;
            else left++;// for case 2,2,2,0,2,2 a[left] == a[mid], 
                        //we just ignore the leftmost one
        }
        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)/2;
            if(a[mid] == target)
                return mid;
            else if(a[mid] < target)
                left = mid+1;
            else
                right = mid -1;
        }
        return -1;
    }
    bool search(int A[], int n, int target) {
        //three steps: cut the array into two sorted arrays;
        //             search the target in tow sorted arrays;
        //             return the index;
        int index = find(A,n);
        int result = false;
        if(index == 0)
            result = binarySearch(A,0,n-1,target);
        else
        {
            if(target >= A[0])
                result = binarySearch(A,0,index-1,target);
            else
                result = binarySearch(A,index,n-1,target);
        }
        if(result != -1) return true;
        else return false;
    }

对于思路二

请参见[LeetCode] Search in Rotated Sorted Array II 解题报告.