이진탐색
이진탐색이란 정렬되어 있는 배열에서 특정 값을 찾아낸다. 오름차순 배열 되어있을 때, 배열의 중간에 있는 임의의 값을 선택해 찾고자하는 값 X와 비교하고 X가 중간값보다 작으면 중간값 기준 좌측 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 ㅌ마색한다. 동일한 방법으로 해당 값을 찾을 때 까지 반복한다.
예시
[ 17, 28, 43, 67, 88, 92, 100 ]에서 43의 위치는?
- 가운데 값 67 > 43 -> 좌측 탐색
- [17, 28, 43]의 가운데 값 28 < 43
- 43은 28 우측에 존재하는데 28우측, 67좌측은 하나밖에 없음. 43==43 원하는 값 찾았으므로 종료
Plain Text
복사
이진 탐색은 만약 N크기의 배열을 탐색한다면 반복마다 N, N/2, N/4, N/8, …, 1 이 횟수만큼 실행될 것이기 때문에 실행된 반복의 횟수가 K라면 2^K = N이 되어야 한다. 따라서 K = log2N으로 이진탐색의 시간복잡도는 O(logN)이다.
이는 파이썬의 bisect 모듈로 구현되어 있습니다.
bisect.bisect() 함수는 정렬된 리스트에 값을 삽입할 때 정렬을 유지할 수 있는 인덱스를 반환합니다.
이게 무슨 말인지 예시로 알아봅시다.
Q. 오름차순 정렬된 자동차 연비를 담은 리스트가 주어진다. 임의로 3개의 값을 뽑았을 때 중앙값이 m일 경우의 수 구하기
연비 리스트
import bisect
mileage = [1, 15, 25, 35, 60, 100] # 연비리스트
m = 60 # 중앙값 60
pos = bisect.bisect(mileage, m) # m을 삽입할 위치를 반환
Python
복사
이 때 pos의 값은 5이다.
즉 index 0~4까지는 m보다 작거나 같다는 것이고, index 5이상은 m보다 크다는 것이다.
그리고 조건으로 주어진 중앙값이 무조건 리스트에 존재한다면 index 4는 m과 같다.
따라서 답은 다음과 같이 구해진다.
answer = (m-1) * (len(mileage)-pos)
Python
복사
적절한 문제에 잘 사용하면 시간복잡도를 매우 줄일 수 있을 것이다.
bisect_left와 bisect_right
bisect_left(a, x)
정렬된 a에 x를 삽입할 위치를 리턴해준다. x가 a에 이미 있으면 기존 항목의 앞 (왼쪽)의 위치를 반환한다.
bisect_right(a, x)
bisect_left와 거의 같은 함수인데, 이번에는 x가 a에 이미 있으면 기존 항목 뒤 (오른쪽)의 위치를 반환한다.
※ 값이 배열에 없을 때는 리턴 값이 일치하다.
