#010_자료구조와 알고리즘_이진 탐색 알고리즘 (Binary Search)

안녕하세요 삽잡이입니다.

이번 시간에는 이진 탐색 알고리즘에 대해서 정리해보려고 합니다.

이진 탐색(Binary Search)은 오름 차순으로 정렬된 리스트가 준비 된 상태에서

처음 중간의 값을 기준으로 탐색 범위를 1/2씩 줄여나가는 알고리즘입니다.

예를들어볼까요?

2 3 4 5 6 7 10 15 20 25 50 57 59 60

이런 오름차순 리스트가 있다고 가정해보도록 하겠습니다.

여기서 저는 57이라는 값을 찾고자 한다면

임의의 수 즉, 데이터 집합의 중앙에 값과 비교를 합니다. 

57은 15 보다 크니 15이하의 데이터들은 모두 배제를 하게 됩니다.

즉, 20 ~ 60까지의 리스트에서 또 중앙의 값과 비교를 시작합니다.

중앙의 값의 50이라고 해보겠습니다.

50보다 57은 크니 50이하의 값은 모두 배제를 하게 되고

57 ~ 60 까지의 리스트에서 또 비교를 하게 됩니다. 결국 57을 찾게 되죠...

오름차순으로 우선 정렬을 해둔 상태여야하는 전제 조건이 있지만,

한번 비교할 때마다 비교해야할 데이터 집합은 1/2로 줄기 때문에 성능이 매누 좋은 점이 있습니다.

다음은 '위키 백과'에서 가져온 이진 탐색 알고리즘의 의사코드입니다.

BinarySearch(A[0..N-1], value, low, high) {
  if (high < low)
    return -1 // not found
  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 // found
}

이상으로 이진 탐색 알고리즘에 대한 소개를 끝내도록 하겠습니다.

지금까지 삽잡이였습니다~!