이분탐색(Binary Search)

이분탐색(Binary Search)

• 입력 : 정렬된 원소리스트, 찾을 값
• 시간복잡도 : log₂ n

이분탐색 과정

정수 배열 int[] array = {2, 5, 8, 10, 15, 16, 19, 20}에서 int key = 8이 몇 번째에 위치해 있는지 찾는다고 가정하자.

Binary Search 과정

1. 가장 먼저 할 일은 탐색 범위를 정하는 것이다. 이 경우에는 주어진 정수 배열 전체를 기준으로 하므로 인덱스 0 ~ 7이 범위가 된다.

2. 탐색 범위가 정해지면 해당 범위의 가운데에 위치한 값을 찾는다. 가운데 값은 탐색 범위의 마지막 인데스에서 첫 인덱스를 뺀 뒤 2로 나눈 수를 인덱스로 가지는 값이다. 이 경우는 (7 - 0) / 2는 3이므로 array[3]의 10이 가운데 값이 된다.

3. key값과 가운데 값(10)을 비교한다.
   1) 값이 서로 같다면 해당 인덱스를 반환
   2) key 값이 가운데 값보다 작다면 가운데 값 이후(가운데 값 포함)를 탐색범위에서 제외시킨다.
   3) key 값이 가운데 값보다 크다면 가운데 값 이전(가운데 값 포함)를 탐색범위에서 제외시킨다.

4. 8은 10보다 작으므로 위의 2)에 해당한다. 따라서 탐색 범위를 0 ~ 2로 변경한다.

5. 원하는 값을 찾을 때 까지 2번, 3번, 4번의 과정을 반복한다. 만약 탐색 범위 내 원소의 개수가 하나가 될 때 까지 key 값을 찾지 못했다면 주어진 원소 배열에 key 값이 존재하지 않다고 결론 내리고 탐색을 종료한다.

위의 3번과정을 진행하기 위해서는 key 값이 중간 값 보다 작은 경우 key 값이 배열안에 존재한다면 반드시 중간 값보다 앞에 위치함을 보장해야한다. 반대의 경우도 마찬가지이다. 따라서 array는 정렬되어 있어야만 한다. 위의 경우는 이미 정렬된 배열을 사용했지만 그렇지 않은 경우 탐색을 진행하기 전에 먼저 원소 배열을 정렬해야 한다.

Java를 이용한 구현

반복을 이용

public int binarySearch(int[] input, int key) {
  int low = 0;
  int high = input.length - 1;
  int mid;

  while (low <= high) {
    mid = (high + low) / 2;

    if (input[mid] == key) {
      return mid;
    } else if (input[mid] > key) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return -1;        // input에 key가 존재하지 않음 
}

재귀를 이용

public int binSearch2(int input[], int key) {
  return binSearch2(input, 0, input.length, key);
}

// 재귀(recursion)
public int binSearch2(int input[], int low, int high, int key) {
  int mid = (high + low) / 2;
  int location = -1;

  while (low <= high && location == -1) {
    if (input[mid] == key) {
      location = mid;
    } else if (input[mid] > key) {
      binSearch2(input, low, mid - 1, key);
    } else {
      binSearch2(input, mid + 1, high, key);
    }
  }

  return location;
}