Das erste Vorkommen in der binären Suche

Question

Ich versuche, das erste Vorkommen der Nummer 5 zu bekommen. Die Antwort sollte in diesem Fall 2 sein, aber ich bekomme 3 hier.

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

Wenn Sie den Wert, den Sie suchen, nicht finden, kehren Sie den mid Index sofort, ohne zu überprüfen, ob es kleinere Indizes mit dem gleichen Wert.

Sie haben die Suche fortzusetzen:

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; 
    }