탐색 알고리즘 - 이진 탐색(Binary Search)

자료구조에서 탐색에 대한 알고리즘을 배운 바 있다.

• 순차 탐색
• 해시 
• 이진 탐색 트리

여기에 추가로 이진 탐색에 대해 알아보자

 

이진 탐색

이분 탐색으로도 불리는 이진 탐색은 '업다운 게임'을 떠올리면 이해하기 쉽다.

30개의 정렬된 원소 중 정확히 70이 든 값을 찾으려면 중간을 까서 이하인지 이상인지 확인하는 방식으로 

찾아 나아가면 된다.

순차 탐색에 비해 이진 탐색의 찾는 속도가 훨씬 빠른 것을 볼 수 있다.

 

이진 탐색은 병합 정렬과 더불어 분할 정복 알고리즘(Divide and Conquer)의 대표적인 예이기도 하다.

Divide: 리스트를 두 개의 서브 리스트로 나눈다.

Conquer: 검색할 숫자 > 중간 값이면 뒷 부분에서, 반대면 앞 부분에서 검색할 숫자를 찾는다.

 

코드

def binary_search(data, search):
  print(data)
  if len(data) == 1 and search == data[0]:
    return True
  if len(data) == 1 and search != data[0]:
    return False
  if len(data) == 0:
    return False
    
  medium = len(data) // 2
  if search == data[medium]:
    return True
  else:
    if search > data[medium]:
      return binary_search(data[medium+1:], search)
    else:
      return binary_search(data[:medium], search)
    
import random
arr = random.sample(range(100), 10)
print(binary_search(sorted(arr), 77))

 

분석

한 번 체크할 때마다 medium 초과인지 미만인지로 나뉘어 2분의 1이 되니까

시간복잡도는 O(logn)