[알고리즘] 이진탐색 파이썬 및 시간복잡도

# 내용

정렬된 데이터 셋에서 탐색을 시도함

함수가 실행될때마다 탐색하는 범위가 반토막이 되기 때문에 순차탐색에 비해 월등히 속도가 빠름

 

# 코드

# 이진탐색은 데이터셋이 정렬되어 있어야함.
import random

def binary_serach(list,target):
  print(f"{list}, target : {target}",end="")
  # 찾는 조건
  if len(list) == 1 :
    if list[0] == target :
      return True
    else :
      return False
  elif len(list) == 0 :
    # binary_serach함수를 호출할때 list[mid+1:]로 슬라이싱 하기 때문에
    # len이 0이 되는 경우가 존재
    return False

  # 탐색 조건
  mid = len(list) // 2
  print(f", mid {list[mid]}")
  if target == list[mid] :
    return True
  elif target < list[mid] :
    return binary_serach(list[:mid],target)
  elif target > list[mid] :
    return binary_serach(list[mid+1:],target)



if __name__ == '__main__':
  list = random.sample(range(20), 10)
  list.sort()
  answer = binary_serach(list, 10)
  print(answer)

 

# 시간복잡도

O(log n)