配列内のキーをバイナリ検索する場合、loまたはhiの最終値は？

Question

ソートされたキー配列を持つ整数キーを仮定します。int[] keys = {10,20,30,40,50,60,70};したがって、最初はランクlo = 0とhi = 6になります。

keys配列の30のバイナリ検索では、loの最終値は20ですか？1ですか？

私は論理を理解する必要があります。

Answer 1

バイナリ検索がそうのように起動します：

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

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

lo = mid + 1 = 2

最後に、30 > 20として、hi = mid - 1 = 2

さて、30 < 40として
lo = 2, hi = 2, mid = 2, numberInMid = 30 、以来
35 > 30として 、lo = mid + 1 = 3、
lo > hi：

30 == 30として

、ループを抜けるとans = 30 代わりに、あなたが探していた場合は、その後、（私はそれが関係式上記のすべてで収まるので、この数を取る）35を言いますループが終了し、デフォルト値のansが返されます。
例：ans = -1正の整数のみが含まれている場合や、代わりに==の式がヒットした場合にのみtrueに切り替わるflag = falseを使用することもできます。

Answer 2

デバッグを理解するために、コードを実装してトレースすることができます。

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