탐색 알고리즘

js·2022년 6월 17일
0

이진 탐색

원리

  • Divide: 리스트를 두개의 서브 리스트로 나눈다.
  • Conquer
    • 검색할 숫자(search) > 중간값이면, 뒷부분의 서브 리스트 에서 검색할 숫자를찾는다.
    • 검색할 숫자(search) < 중간값이면, 앞부분의 서브 리스트 에서 검색할 숫자를찾는다.

코드 구현

재귀함수로 이진 탐색을 구현한 코드. 리스트의 절반에 위치한 요소와

검색하는 값을 비교한 뒤 리스트 슬라이싱을 하고 나서 재귀함수를 호출한다.

그렇게 되면, 리스트의 크기는 절반씩 타노스(?) 당할 것이고 결국엔 찾고자 하는 값을 발견하면 true를 리턴하는 코드이다.

def binary_search(data,search):
  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:],search)
    else:
      return binary_search(data[:medium],search)

시간 복잡도

n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교 연산을 k회진행

결국 O(log2n+1)이고, 2와1, 상수는 삭제되므로, O(logn)

0개의 댓글