[알고리즘] 이진 탐색(Binary search)

💡이진 탐색(Binary search)이란?

이진 탐색 알고리즘이란 정렬된 데이터 내에서 특정 값을 검색할 때 탐색 범위를 절반씩 좁혀가며 탐색하는 알고리즘이다. 탐색 범위가 반씩 줄어들기 때문에 O(logN)의 시간복잡도를 가진다. 단, 정렬된 데이터에서만 쓸 수 있다는 단점이 있다.

def binary_search(st,ed,value): # 시작, 끝, 찾을 값
    while (1):
        mid=(st+ed)//2          # mid
        if arr[mid]==value:     # mid가 target과 같을 경우
            return 1
        elif arr[mid] > value:  # mid가 클 경우
            ed=mid-1
        elif arr[mid]<value:    # mid가 작을 경우
            st=mid+1
        if st>ed:               # 종료 조건
            return 0

n=int(input())
arr=list(map(int,input().split())) #배열 입력
target=int(input()) # 찾을 값

arr.sort() # 정렬
flag = binary_search(0,n-1,target)
if flag:
    print("찾음")
else:
    print("없는숫자")

• 필요한 변수
  • start: 탐색 범위의 처음
  • end: 탐색 범위의 끝
  • mid: 탐색 범위의 중간
• 종료 조건
  • end < start: 검색에 실패할 경우
  • arr[mid] == target: 검색에 성공할 경우
• 시간 복잡도(Time complexity)
  • Best: O(1) / Average: O(logN) / Worst: O(logN)

Python bisect 라이브러리

Python에는 이진 탐색을 쉽게 사용할 수 있는 라이브러리가 존재한다.

• bisect_left(a, x)
  • 정렬을 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 반환한다.
• bisect_right(a, x)
  • 정렬을 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 반환한다.

from bisect import bisect_left, bisect_right

a = [0,1,2,3,4,5,6,7,8,9]
x = 5

print(bisect_left(a, x)) # 5
print(bisect_right(a, x)) # 6