이진탐색 구현 (Binary Search)

다음의 배열이 있다고 치자.

int[] array = {1,4,2,5,6,9,141,552};

그리고 141이라는 숫자를 빠르게 이진탐색으로 찾아가야 한다.

시그니처는 다음과 같이 잡자

public static int  binarySearch (int[] array, int key)

다만 이 메서드에 마구 array를 집어넣으면 안되고, 이진탐색의 경우 필수적인 조건이 sort를 해주어야 한다. array는 다음과 같이 간단하게 sort가 가능하다.

Arrays.sort(array);

이제 구현을 해보자

 public static int  binarySearch (int[] array, int key) {
  
  int upper = array.length - 1;
  int lower = 0;
  
  while(upper >= lower) {
   
   int i = (upper + lower) / 2;
   
   if      (array[i] == key) return i;
   else if (array[i] > key)  upper = i - 1;
   else if (array[i] < key)  lower = i + 1;
  }
  
  return -1;
  
 }

간단한건데, 일단 최대 찾는 상한선을 받은 배열의 length - 1로 준다. 배열은 0부터 시작해서 그렇다. 따라서 결론적으로는 array[0] ~ array[length-1] 을 뒤지게 된다.

상한선이 하한선보다 위에 위치하고 있을때만 루프문을 도는건 자명하고, i의 경우 상한선과 하한선의 정확히 중간을 찾아야 하므로 2를 나눠준다. 일단 나머지등은 그냥 생각하지않는다.

분기문에서는 총 세가지,

1) 답을찾았을경우 index를 리턴하고,

2) 그보다 클 경우 상한선을 방금 뒤진 index보다 하나 작은 값으로 넣어준다 .(검색범위 반절로 줄음)

3) 그보다 작을경우 하한선을 방금뒤진 index보다 하나 큰값을 넣어준다. (검색범위 반절로 줄음)

간단하다.

다만, 이걸 구현할 필요없이 Arrays.binarySearch를 이용하면 그냥 쓸수있다.