Für binäre Suche nach Schlüsseln in einem Array, was ist der endgültige Wert von lo oder hi?

Question

Nehmen Sie Integer-Schlüssel mit sortierten Tasten Array: int[] keys = {10,20,30,40,50,60,70}; Also zunächst in den Rang lo = 0 und hi = 6.

Für binäre Suche nach 30 in der Schlüssel-Array, wäre der Endwert von lo 20, was 1 ist?

Ich muss nur die Logik verstehen.

Answer 1

Binary Suche beginnen würde, etwa so:

lo = 0, hi = 6, mid = 3, numberInMid = 40 

Als 30 < 40, hi = mid - 1 = 2

Nun
lo = 0, hi = 2, mid = 1, numberInMid = 20

Als 30 > 20, lo = mid + 1 = 2

Schließlich
lo = 2, hi = 2, mid = 2, numberInMid = 30

Als 30 == 30, Schleife beendet und ans = 30 Wenn stattdessen Sie für die Suche sagen 35 (ich diese Nummer übernehmen, da sie mit allen oben relationalen Ausdrücke passt), dann gilt:
Als 35 > 30, lo = mid + 1 = 3,
Da lo > hi , Schleife beendet und Sie erhalten den Standardwert ans.
ZB: ans = -1 Wenn nur positive ganze Zahlen beteiligt sind oder stattdessen, können Sie sogar eine flag = false verwenden, die nur auf true umschaltet, wenn ein == Ausdruck gefunden wird.

Answer 2

Sie können den Code implementieren und verfolgen Sie durch debug für das Verständnis.

public class Test { 
    public int binary_search(int[] keys, int low, int high, int mid, int target){ 
     if(low > high){ 
      return -1; 
     } 

     if(target < keys[mid]){ 
      high = mid - 1; 
      mid = (low + high)/2; 
      return binary_search(keys, low, high, mid, target); 
     }else if(target > keys[mid]){ 
      low = mid + 1; 
      mid = (low + high)/2; 
      return binary_search(keys, low, high, mid, target); 
     }else{ 
      return mid; 
     } 
    } 

    public static void main(String args[]){ 
     int[] keys = {10,20,30,40,50,60,70}; 
     Test test = new Test(); 
     int mid = (0 + keys.length)/2; 
     int target = 30; 
     int index = test.binary_search(keys, 0, keys.length, mid, target); 
     System.out.println(index); 
    } 
}