CSwithPYTHON - 이진 검색

이진 검색(탐색) / Binary Search

• 이진 검색은 자료의 가운데에 있는 항목 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법이다.
• 목적 키를 찾을 때 까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행할 수 있다.
• 이진 검색을 하기 위해서는 자료가 정렬된 상태이여야 한다.
  -> 사실 정렬도 비용이지만, 정렬하는 비용을 포함해도 이진 검색은 굉장히 효율적인 방법이므로 많이 쓰인다.

이진검색의 특징

1. 검색과정은 다음과 같다
   1. 자료 중앙의 원소를 고른다.
   2. 1번에서 고른 원소와 찾고자 하는 목표값을 비교한다.
   3. 만약 목표값이 고른 값보다 작으면 고른 값에 왼쪽 구간에서 검색을 새로 수행하고,
      만약 목표값이 고른 값보다 크다면 고른 값에 오른쪽 구간에서 검색을 새로 수행한다.
   4. 목표값을 찾을 때 까지 1~3번을 반복한다.
2. 만약 자료의 삽입이나 삭제가 발생한다면, 배열의 상태를 다시 정렬 상태로 유지하는 추가 작업이 필요하다.

이진 검색의 중요성

1. 큐를 통해 버퍼를 이해할 수 있다.
2. 큐와 버퍼의 이해를 스택에 대한 이해와 결합시키면 Breadth-First Search, 즉 BFS에 대해 이해할 수 있다. 이는 우리가 기초적으로 이해해야 할 스택 - 재귀호출 - DFS - Memoization - DP 흐름을 이해하는 데 크나큰 도움이 된다.
3. 최악의 시간복잡도 O(n)은 log2N이다.

이진 검색의 구현

1. while로 구현하기

   • 인덱스 활용

   def binary_search(arr, lo, hi, key):
   # 중간 위치 선택
   while lo <= hi:
       mid = (lo + hi) // 2
       if arr[mid] == key:
           return mid
       elif arr[mid] > key:
           hi = mid - 1
       else:
           lo = mid + 1
   return -1
   
   
   arr = [8, 11, 16, 28, 39, 49, 60, 67, 85, 89]
   N = len(arr)
   print(binary_search(arr, 0, N - 1, 67))
   print(binary_search(arr, 0, N - 1, 68))

   • 재귀 함수 활용

   def binary_search_recur(arr, lo, hi, key):
   if lo >= hi: return -1
   mid = (lo + hi) >> 1
   if arr[mid] == key:
       return mid
   elif arr[mid] > key:
       return binary_search_recur(arr, lo, mid - 1, key)
   else:
       return binary_search_recur(arr, mid + 1, hi, key)
   
   arr = [8, 11, 16, 28, 39, 49, 60, 67, 85, 89]
   N = len(arr)
   print(binary_search_recur(arr, 0, N - 1, 67))
   print(binary_search_recur(arr, 0, N - 1, 68))
   

   ver 230505 첫 작성