在旋轉N次的數組中搜索一個元素

Question

我有一個有序數組，它旋轉了n次，n是未知的。現在我想在O（nlog n）中使用二分搜索搜索一個元素。我實現了以下代碼，它工作正常。 但我認爲條件如果（（結束開始）== 1）可以通過做一些修改， 可以跳過任何人建議？

Eg of array 1 2 3 4 5 
      2 3 4 5 1 //rotated once 

代碼：

public static int srch(int a[],int start,int end,int key){ 
    if(start>end) 
     return -1; 

    if((end-start)==1){ 
     if(key==a[start]) 
      return start; 
     else if(key==a[end]) 
      return end; 
     else 
      return -1; 
    } 
    int mid = (start+end)/2; 

    if(a[mid]== key){ 
     return mid; 
    } 
    else{ 
     if(a[start] < a[mid]){ 
      //first half is sorted 
      if(key>a[mid]|| key <a[start]){ 
       start= mid+1; 
      }else{ 
       end =mid-1; 
      } 
     }else{ 
      //second half is sorted 

      if(key>a[mid]){ 
       start= mid+1; 
      }else{ 
       end =mid-1; 
      } 
     } 
     return srch(a, start, end, key); 
    } 
} 

沒有更好的/簡單/更有效的解決方案？

Answer 1

您的解決方案在O（日誌n）中運行，因此不能有更高效的解決方案。也許你的部分代碼可以優化，但是不會影響O的運行時間。正如你所說的，代碼工作並返回正確的值，因此我認爲這是你的面試問題的正確答案。

Answer 2

我沒有徹底檢查您的代碼的正確性，但您的解決方案是O（日誌n）。算法上不能有更好的解決方案。

Answer 3

您的解決方案失敗了陣列{4,5,1,2,3}和鍵= 4。 我認爲在第二部分的變形就能解決問題

else{ 
      //second half is sorted 

      if(key>a[mid] && key<=a[end]){// modified condition 
       start= mid+1; 
      }else{ 
       end =mid-1; 
      } 

但是我認爲條件 如果（（端開始）== 1）可以通過使 一些修改被跳過，任何一個可以 建議？

我想這種情況根本不需要。 你能建議你的修改代碼失敗的測試用例嗎？

public static int srch(int a[],int start,int end,int key){ 
    if(start>end) 
     return -1; 

    int mid = (start+end)/2; 

    if(a[mid]== key){ 
     return mid; 
    } 
    else{ 
     if(a[start] < a[mid]){ 
      //first half is sorted 
      if(key>a[mid]|| key <a[start]){ 
       start= mid+1; 
      }else{ 
       end =mid-1; 
      } 
     }else{ 
      //second half is sorted 

      if(key>a[mid] && key<=a[high]){ 
       start= mid+1; 
      }else{ 
       end =mid-1; 
      } 
     } 
     return srch(a, start, end, key); 
    } 
}