배열의 키에 대한 이진 검색의 경우 lo 또는 hi의 최종 값은 무엇입니까?

Question

정렬 키가있는 정수 키 배열을 가정합니다. int[] keys = {10,20,30,40,50,60,70}; 처음에는 순위가 lo = 0 및 hi = 6입니다.

키 배열에서 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

30 == 30, 루프 종료 및 ans = 30 대신 것처럼, 당신이 검색 한 다음, (이 관계식 위의 모든에 적합하기 때문에 나는이 숫자를 가지고) 35 말 :
35 > 30, lo = mid + 1 = 3, 이후
, lo > hi로 루프가 종료되고 기본값 ans이 리턴됩니다.
예 : ans = -1 양수 만 포함 된 경우 == 표현식에 도달하면 flag = false을 true로 전환 할 수도 있습니다.

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