리스트 검색하기

이진 검색은 어떻게 구현하는가?

리스트가 정렬되어 있지 않으면 리스트 검색 시 주어진 값에 맞는 원소를 찾기 위해 리스트를 모두 찾아봐야 한다. 하지만 정렬된 리스트가 있거나 검색하기 전에 정렬을 수행한 상황이라면 리스트에서 값을 찾을 때 이진 검색^{binary search}을 사용하는 것이 매우 효율적이다.

method binarySearch(list l, element e):
  if l is empty:
    return false

  let value = l(l.size / 2)

  if (value == e):
    return true

  if (e < value):
    return binarySearch(elements between l(0) and l(l.size / 2 - 1)
  else:
    return binarySearch(elements between l(l.size / 2 + 1) and l(l.size)

이 알고리즘은 정렬된 리스트의 속성을 이용한다는 장점이 있다. 즉, 많은 원소가 주어진 원소와 맞지 않다는 걸 이미 알고 사용하는 것이므로 원소를 일일이 비교해보지 않고도 주어진 원소를 찾을 수 있다. 만약 백만 개의 원소가 있따면 20번 미만의 비교로도 주어진 원소를 찾을 수 있다. 따라서 이 알고리즘의 성능은 O(n)이다.

코드 4-10은 이진 검색을 구현한 예이다.

[코드 4-10]이진 검색 구현하기

public static boolean binarySearch(final List numbers, final Integer value) {
  if(numbers == null || numbers.isEmpty()) {
    return false;
  }

  final Integer comparison = numbers.get(numbers.size() / 2);
  if (value.equals(comparison)) {
    return true;
  }

  if (value < comparison) {
    return binarySearch(numbers.subList(0, numbers.size() / 2), value);
  } else {
    return binarySearch(numbers.subList(numbers.size() / 2 + 1, numbers.size()), value);
  }
}