출처

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search

이분 탐색

위의 사진 자료가 모든 것을 다 표현해주는 것 같다.

• 이분 탐색은 정렬이 되어있는 배열에서 ‘재귀’를 이용하여 탐색 범위를 줄여가며 데이터를 검색하는 방법

  • 재귀가 사용이 가능하다는 말 ⇒ 반복문으로 구현이 가능하다는 말

• 순차적인 방법은 O(N)이지만 ‘반’씩 범위를 줄여가며 찾는 이분 탐색은 O(logN)의 시간 복잡도를 가지고 있어, 아주 큰 데이터에 원하는 값을 찾는데 적합하다.

구현 코드

• 위의 그림 자료를 보고 직접 작성을 해 보았다.

arr = [3,4,1,6,8,10,42,11,22,18]

#정렬
arr.sort()

start = 0
end = len(arr) - 1

num = int(input("찾는 숫자: "))

def BinarySearch(arr,start,end,target):
    mid = (start+end)//2

    if arr[mid] == target:
        return mid
    elif start > end:
        return None
    
    if arr[mid] > target:
        return BinarySearch(arr,start,mid - 1,target)
    else:
        return BinarySearch(arr,mid+1,end,target)

print(BinarySearch(arr,start,end,num))

start,end의 index를 지정해줘서 범위를 점차 줄여 나가면서 내가 원하는 숫자를 탐색하는 것.

단점

• 이분 탐색은 정렬된 고정 크기 데이터에서 탐색을 해야 효율적이다.

• 데이터가 자주 삽입,삭제,정렬이 불가능 한 경우에는 해시 테이블, B - 트리 같은 다른 자료구조가 더 나은 성능을 제공한다.

Python 라이브러리

• bisect (binary select의 준말..? 라이브러리를 사용한다.

• 두 가지의 함수 존재
  - bisect_left(a,x)
  - 정렬된 순서 유지하며 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 함수
  - bisect_right(a,x)
  - 정렬된 순서를 유지하며 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 함수

글로 보니까 잘 이해가 안되어서 직접 구현해 봤다.

from bisect import bisect_left,bisect_right

arr = [1,2,4,5,6]
arr.sort()
x = 3

print(bisect_right(arr,x))

#2

arr2 = [1,2,2,2,3,3,6,6,6]
y = 3

print(bisect_left(arr2,y))
# 4

말 그대로 right는 찾는 숫자가 들어갈 가장 오른쪽 index를 반환, left는 찾는 숫자가 들어갈 가장 왼쪽 index를 반환.