在二進制搜索中獲得第一個匹配

Question

我試圖獲得第一個匹配的數字5。在這種情況下，答案應該是2，但我在這裏得到3。

public static void main(String[] args) { 
      int A[] = {1, 3, 5, 5, 5, 17, 20}; 
      int index = BinarySearch(A, 5); 
      System.out.println(index); 
     } 

     public static int BinarySearch(int[] A, int x) { 
      int low = 0; 
      int high = A.length - 1; 

      while (low <= high) { 
       //(low + high)/2 
       int mid = low + (high-low)/2; // more optimal -> low + (high-low)/2 (avoid integer overflow) 
       if (x == A[mid]) { 
        return mid; 
       } else if (x < A[mid]) { 
        high = mid - 1; 
       } else { 
        low = mid + 1; 
       } 
      } 
      return -1; 
     } 

Answer 1

當你發現你正在尋找的價值，你立即返回mid指數如果不存在具有相同值的索引檢查。

你必須繼續搜索：

public static int BinarySearch(int[] A, int x) { 
     int low = 0; 
     int high = A.length - 1; 
     int mid = -1; 
     while (low <= high) { 
     mid = low + (high-low)/2; 
     if (x <= A[mid]) { // this ensures you keep searching for the first index having 
          // the number you are looking for 
          // 
          // changing x <= A[mid] to x < A[mid] will give you the 
          // last index having the number you are looking for instead 
      high = mid - 1; 
     } else { 
      low = mid + 1; 
     } 
     } 
     if (mid >= 0 && x == A[mid]) { 
     return mid; 
     } 
     return -1; 
    }