搜索排序和旋轉數組中的元素

我需要搜索排序和旋轉數組中的元素（數組可能包含重複元素）。排序和旋轉數組表示排序後的數組由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); 

     } 


}

上述代碼在重複元素的數組中失敗。任何人都可以改進？

來源

2013-06-26 bhavneet

如果你正在使用快速排序，我建議用最右邊的元素交換樞軸，然後在分區之後恢復它。這樣你可以處理重複。 – Nobilis

可能重複[在旋轉的排序數組中搜索數字]（http://stackoverflow.com/questions/1878769/searching-a-number-in-a-rotated-sorted-array） –

你能解釋一下你在做什麼正確的意思是擺脫？ – pkacprzak

一個可能的答案可能是......

1）首先找到最小元素並按排序順序排列。

  Complexity : worst-case O(n)

2）通過二分查找搜索所需的元素。

  Complexity : log(n)

來源

2016-09-23 18:02:33

搜索排序和旋轉數組中的元素

回答

相關問題