修改後的二進制搜索java

Question

所以我遇到了一個巨大的障礙....也許這只是因爲我的邏輯不存在，但我似乎無法自己弄清楚這一點。

我試圖修改BinarySearch以便它會獲得兩個索引。

首先索引是給定的數，X，和最右側的最遠左手食指。如果該數字不存在，則它會生成[-1，-1]。

反正。我一直在嘗試修改BinarySearch並且似乎無法使其工作。任何指針將不勝感激。

public static Pair BinarySearchDup(int[] A, int x, int low, int high){ 
    int mid = (low + high)/2; 
    int left = -1, right = -1; 
    while(low <= high){ 
     mid = (low + high)/2; 
     if(A[mid] == x){ 
      int newMid = mid; 
      //check left 
      if(left == -1){ 
       left = mid; 
       return BinarySearchDup(A, x, low, mid - 1); 
      } 
      else if(right == -1){ 
       right = mid; 
       return BinarySearchDup(A, x, newMid + 1, high); 
      }  
      return new Pair(left, right); 
     } 
     else if(A[mid] < x) 
      return BinarySearchDup(A, x, mid + 1, high); 
     else// (A[mid] > x) 
      return BinarySearchDup(A, x, low, mid - 1); 
    } 
    //if there are no matches of the number then it returns -1 
    return new Pair(-1, -1); 
} 

Answer 1

爲了解決這個問題：

我試圖修改二分查找，這樣它會獲得兩個指標。 第一個索引是給定數字x最右邊的最左邊的索引。如果該數字不存在，則它會生成[-1，-1]。

我這樣做：

1）做一個二進制搜索，除了沒有考慮目標的匹配和結束的時候了，認爲這是不是你的目標較大（比如你搜索留下的話） 。當這個搜索結束時，它會在目標的最左邊的實例上，剩下一個（取決於它是如何編碼的 - 在這種情況下只是檢查一個右邊），否則它將被確認不存在。

2）進行二進制搜索，如1）除了考慮目標小於你的目標。這將以類似的方式找到目標的最右邊的實例。

這給你O（logN）的複雜性。 Petar Ivanov的想法是「你不能只用普通的二分搜索，然後簡單地從找到的索引來回移動，直到你得到整個範圍？」如果數組中存在大量重複項，則可能與O（N）一樣差。但是，如果預期的重複計數（或預期的數組大小）很小，那麼Petar Ivanov的想法要簡單得多，因爲您不必使用更改的邏輯重新開始二進制搜索。

Answer 2

我不知道我理解你的想法，但在這裏就是爲什麼它不工作：

您的代碼就相當於：

public static Pair BinarySearchDup(int[] A, int x, int low, int high){ 
    int mid = (low + high)/2; 
    if(low <= high){   
     if(A[mid] == x) 
      return BinarySearchDup(A, x, low, mid - 1); 
     else if(A[mid] < x) 
      return BinarySearchDup(A, x, mid + 1, high); 
     else// (A[mid] > x) 
      return BinarySearchDup(A, x, low, mid - 1); 
    } 

    return new Pair(-1, -1);   
} 

事實上，如果你輸入的同時，循環，你總是回來，所以永遠不會有一次以上的迭代。如果mid的值是x，那麼因爲left是-1，所以你總是輸入這個if子句。或者，如果您不輸入while循環，則只返回（-1，-1）。 希望這有助於。

編輯： 難道你不能只使用普通的二進制搜索，然後簡單地來回找到的索引，直到你得到整個範圍？