이진검색이란?(binary search)

이진검색이란?

이진검색 또한 선형검색과 동일하게 검색 알고리즘의 일종입니다. 이진검색은 기본적인 조건으로 데이터가 정렬되어 있어야 하며, 선형 검색에 비해 빠르게 검색이 가능합니다. 이진검색의 기본적인 시간복잡도는 O(logn)이며, 종료조건은 아래와 같습니다

1. 검색성공 : 검색범위 정중앙값이(pc) 찾고자 하는 값과 동일할때
2. 검색실패 : 검색범위가 더이상 없는경우

이진검색 원리는 검색하고자 하는 배열의 중앙 index의 값을 기준으로 검색범위를 좁혀나가는 원리입니다. 아래 예시를 설명할때 우선 검색범위의 첫번째 인덱스를 pl, 마지막 인덱스를 pr,정중앙 인덱스를 pc라고 예를 들겠습니다

예를 들어서 [1,2,3,4,5,6,7,8,9] 라는 배열이 있으며 나는 여기서 3을 찾고싶다고 가정해봅시다.

1. [pl : 0, pr : 8] 이진검색에서 pc를 지정할때는 (pl + pr) // 2 값으로 지정합니다. 그러면 pc는 4가 됩니다. 인덱스 4의 값은 5이며 이는 3보다 큰 값이 됩니다. 

2. [pl : 0, pr : 3] 그렇기 때문에 검색 범위를 pl을 유지하고, pr에 대해 pc -1 값을 하여 검색범위를 index 0~3으로 줄입니다. 여기서 pc는 1이 됩니다.

3. [pl : 2, pr : 3] 이 검색범위의 pc는 1, index 1의 값인 2보단 큰 값이므로 검색범위를 pl에 대해 pc + 1로, pr은 유지하여 검색범위를 줄입니다. 여기서 pc는 2가 됩니다

4. [pl : 2, pr : 3] 그 다음 검색범위에서 정중앙(pc)index는 2인데, index 2번에는 우리가 찾고자 하는 값인 '3'이 들어있는것이다. 그러면 pc값을 반환하면 되는것이다.

글로 설명하느라 다소 복잡한 감이 있습니다. 간단하게 요약하면 이진검색에서 검색범위를 줄이는 과정은 아래 두가지와 같습니다

1. a[pc] < key : 정중앙값이 찾고자하는 값보다 작은 경우이며 pl값을 pc + 1로 변경하여 검색범위를 줄인다.

2. a[pc] > key : 정중앙값이 찾고자하는 값보다 큰 경우이며 pr값을 pc -1로 변경하여 검색범위를 줄인다.

예제 코드는 아래와 같습니다

from typing import Any, MutableSequence

def binary_search(arr : MutableSequence, key : Any) -> int:
  # 검색범위 맨 첫번째 인덱스
  pl = 0
  # 검색범위 맨 마지막 인덱스
  pr = len(arr) - 1
  while True:
      #검색범위 중앙의 인덱스
      pc = (pl + pr) // 2
      #중앙값이 찾고자하는 key일때
      if arr[pc] == key:
          return pc
      #중앙값이 찾고자하는 키값보다 작은경우
      elif arr[pc] < key:
          pl = pc + 1
      #중앙값이 찾고자하는 키값보다 큰 경우
      elif arr[pc] > key:
          pr = pc - 1
      # 검색범위 첫번째 index번호가 마지막 index번호보다 커진 경우
      if pl > pr:
          return -1

if __name__=="__main__":
  print(binary_search([5,7,15,28,29,31,39,58,68,70,95], 28))