c - ソートおよびピボットされた配列内の要素を検索する

Question

ソートおよびピボットされた配列内の要素を検索する必要があります (配列には繰り返し要素が含まれる場合があります)。ソートおよびピボットされた配列とは、ソートされた配列が k 要素だけ回転されることを意味します。

int sortedpivot( int arr[], int start , int end , int x)
{
        if ( start > end ) return -1;

        if ( start == end ) return x== arr[start]? start : -1;

        int mid = ( end - start ) /2 + start ;
        if ( arr[ mid] == x) return mid;

        if ( arr[ mid] > arr[ start])
        {
                if (    x< arr[ mid] && x>= arr[ start])
                        return sortedpivot( arr, start , mid-1, x);
                else
                        return sortedpivot( arr, mid + 1, end , x);

        }

        else
        {
                if (    x> arr[ mid] && x<= arr[ end])
                        return sortedpivot( arr, mid+1, end, x);
                else
                        return sortedpivot( arr, start, mid-1 , x);

        }


}

上記のコードは、要素が繰り返される配列では失敗します。誰でも改善を提案できますか？

Answer 1

1つの可能な答えは..

1) 最初に最小要素を見つけて、ソート順に作成します。

         Complexity : worst-case O(n)

2) 二分探索で目的の要素を検索します。

         Complexity : log(n)