[알고리즘 이론] 이진 탐색 알고리즘

Programming/Algorithm

[알고리즘 이론] 이진 탐색 알고리즘

Yejii 2021. 3. 2. 12:03

이진 검색 알고리즘이란?

: 오름차순으로 정렬된 리스트에서 특정한 값(X)의 위치를 찾는 알고리즘

가장 쉬운 예시로 책 페이지를 찾는 경우를 생각할 수 있다.

선생님이 168페이지를 피라고 말씀하신다면, 우리는 우선 가지고 있는 책을 반으로 갈라 페이지를 확인할 것이다.

펼친 페이지가 168페이지보다 크다면 더 앞의 페이지를 확인할 것이고, 168페이지보다 적다면 더 뒤의 페이지를 확인할 것이다.

이런 방식으로 임의의 중간값을 설정하여 목표값보다 큰지 작은지 판별하며 범위를 줄여나가는 탐색방법을 이진 탐색이라고 한다.

- 장점: 탐색할 때마다 범위가 1/2로 줄어들기 때문에 선형 탐색보다 훨씬 빠르다. (선형탐색 : O(N^2), 이진탐색: O(NlogN))

- 단점: 탐색할 리스트가 오름차순으로 정렬된 경우에만 사용할 수 있다.

기본적인 탐색방법은 다음과 같다.

1. 리스트의 중앙값(arr[mid])을 선택하여 그 값과 찾고자 하는 값의 크고 작음을 비교한다.

2. 만약 중앙값(arr[mid])이 찾는값(X)보다 크면, 중앙값 이후의 범위는 탐색할 필요가 없으므로 범위의 최대 인덱스(high)을 중앙값 - 1(mid - 1)로 초기화한다.

- if (arr[mid] > X) high = arr[mid] - 1;

3. 만약 중앙값이 찾는값(X)보다 작으면, 중앙값 이전의 범위는 탐색할 필요가 없으므로 범위의 최소 인덱스(low)을 중앙값 + 1(mid + 1)로 초기화한다.

- if (arr[mid] <= X) low = arr[mid] + 1;

4. 새로운 범위에서 탐색을 계속 한다....

5. 탐색을 반복하다가 최소 인덱스가 최대 인덱스보다 크거나 같아지면 탐색을 종료한다.

- while(high <= low)

의사코드

BinarySearch(arr[0...N-1], X, low, high){ // 탐색할 리스트, 목표값, 최소인덱스, 최대인덱스
   low = 0
   high = N - 1
   
   if (high <= low)
      return -1 // not found
   mid = (low + high) / 2
   if (arr[mid] > X) // 중앙값보다 목표값이 더 작다면
      return BinarySearch(arr, X, low, mid - 1) // 탐색 범위를 low ~ mid-1로 줄여 재탐색
   else if (arr[mid] < X) // 중앙값보다 목표값이 더 크면
      return BinarySearch(arr, X, mid + 1, high) // 탐색 범위를 mid + 1 ~ high로 줄여 재탐색
   else // 중앙값과 목표값이 같다면
      return mid // found
}