20210617

이진 탐색(Binary Search)

이진 탐색은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

또한 Linked List 같은 것에 이진 탐색을 쓰기 곤란하다. Linked List는 테이프같은 구조라 무작위 위치로 점프하지 못하고 앞뒤로 움직이기만 가능하기 때문이다.
노드를 타고 중앙값을 찾는 방식으로 Linked List에 적용할 수 있지만 추가적인 시간이 소요되므로 비효율적이다.

이진 탐색을 의사 코드로 표현하면 아래와 같다.

BinarySearch(A[0..N-1], value, low, high) {
  if (high <= low)
    return -1 // 찾지 못한 경우
  mid = (low + high) / 2
  if (A[mid] > value)
    return BinarySearch(A, value, low, mid-1)
  else if (A[mid] < value)
    return BinarySearch(A, value, mid+1, high)
  else
    return mid // 찾은 경우
}