20로그 - 10억 개 전화번호에서 이름 찾기 : 이진 검색

이진 검색 (binary search)

• 시간복잡도
  • 이분 탐색 : O(logN)
• 정의
  • 항목들을 두 그룹으로 나누고 각 요소를 비교하는 단계를 거치면서 한 쪽 그룹은 다음 고려 대상에서 제외하는 방법
• 특징
  • 오름차순이나 알파벳 순 등으로 이미 정렬되어 있어야 함
  • 분할 정복(Divide and Conquer) 전략의 예
  • 각 단계마다 남아있는 항목이 절반이 됨
  • 작업의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가함
• 구성
  • 단계의 수(비교 횟수)
    • 전체 항목 크기를 2로 나눠 항목 크기가 1에 도달하게 되는 횟수
  • 2를 거듭지곱했을 때 전체 항목의 수가 되도록 하는 지수
• 사례
  • 로그 : 어떤 수를 2로 나눠 1에 도달하기 까지의 횟수 or 2를 거듭제곱해서 그 수까지 도달하기 까지의 횟수
  • 스포츠 경기의 단계별 토너먼트
  <aside> 💡 [예] 약 2만개의 이름이 포함된 전화번호가 있을 때, 20,000은 $2^{14}$(16,384) 와 $2^{15}$(32,768)의 사이에 있기 때문에 14~15번 사이에 특정 전화번호를 찾을 수 있다.
• </aside>

더 알아보기 (요약)

• 설명
  • 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
  • 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.
• 장점
  • 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.
• 단점
  • 검색 원리상 정렬된 리스트에만 사용할 수 있다.
• 의사코드

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*
}

• high와 low를 지정

binarySearch(A[0..N-1], value) {*//k*  
	low = 0
  high = N - 1
  **while** (low <= high) {
      mid = (low + high) / 2
      **if** (A[mid] > value)
          high = mid - 1
      **else** **if** (A[mid] < value)
          low = mid + 1
      **else** 
          **return** mid *// found k*  
	}
  **return** -1 *// not found k*
}

 

 

분할 정복(Divide and conquer)

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법
• 예) 퀵정렬 (quick sort), 병합 정렬 (merge sort), 고속 푸리어 변환 (FFT) 문제 등
• 대표적인 사례: 하노이의 탑

장점

• 어려운 문제를 간단하게 해결할 수 있다.

단점

• 스택에 많은 데이터를 담고 있어 스택 오버플로가 발생하거나 메모리를 과하게 사용하게 된다.
• 재귀적으로 많은 함수호출이 이루어지면 오버헤드가 발생할 수 있다.
• 문제를 쪼개는 방법 자체가 상당히 어려울 수 있다.

재귀함수로의 표현

function F(x):
  if F(x)의 문제가 간단 then:
    return F(x)을 직접 계산한 값
  else:
    x를 y1, y2로 분할
    F(y1)과 F(y2)를 호출
    return F(y1), F(y2)로부터 F(x)를 구한 값

빠른 실행이나 문제 해결 순서 선택을 위해, 재귀호출을 사용하지 않고 스택, 큐 등의 자료구조로 분할 정복법을 구현할 수 있다.

참고자료

• Branch and Bound - Binary Search
• 이진 검색 알고리즘
• 분할 정복 알고리즘
• 분할 정복