나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다.
코드 출처: https://github.com/ndb796/python-for-coding-test
▶ 이진탐색이란?
정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점, 끝점, 중간점을 이용해 탐색 범위를 설정한다.
찾고자 하는 값보다 중간값이 크면 오른쪽에 위치한 데이터는 중간값보다 큰값들이므로 모두 무시하고 왼쪽에 위치한 데이터들을 범위로 잡고 시작값, 중간값, 끝값을 다시 설정한다. 이를 반복하다 중간값이 찾고자하는 값과 같으면 실행이 종료된다.
- 시간복잡도: 데이터를 탐색할 때마다 탐색범위가 반씩 좁혀지기 때문에 O(logN)이다. 데이터를 처음부터 탐색해야하는 순차탐색이 최악의 경우 O(N)의 시간복잡도를 가지는 것에 비해 이진탐색은 빠르게 탐색을 수행할 수 있다. 탐색범위가 2,000만을 넘어가거나 데이터 개수나 값이 1,000만 단위 이상으로 넘어가면 이진탐색을 유용하게 사용할 수 있다.
▷ 예시
[0,1,4,5,7,8,9]
위의 리스트에서 4를 찾는다고 가정해보자.
- 시작값은 0, 끝값은 9이다. 중간값은 6//2인 3의 위치에 있는 (소수점은 버림) 5이다. 5와 4를 비교해보았을 때 중간점의 값이 더 크므로 5를 포함하여 5의 오른쪽에 있는 리스트들은 모두 무시하고 탐색을 다시한다. -> 0,1,4
- 시작값은 0, 끝값은 4이다. 중간값은 1이다. 중간값 1과 4를 비교해보았을 때 1이 더 작으므로 이번엔 1을 포함한 왼쪽의 리스트들을 모두 무시한다 -> 4
- 시작값이자 끝값이자 중간값인 4를 찾았으므로 종료한다.
▷ 구현
▶ 이진탐색 라이브러리
- bisect라이브러리
- bisect_left(lst,x): lst에서 x의 바로 왼쪽 위치를 반환한다.
- bisect_right(lst, x): lst에서 x의 바로 오른쪽 위치를 반환한다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| 다이나믹프로그래밍(1) (2) | 2021.07.01 |
|---|---|
| [프로그래머스 | 파이썬3] 이진탐색 (2) / 입국심사 (0) | 2021.07.01 |
| 정렬 (1)/ 선택정렬, 삽입정렬, 퀵정렬, 계수정렬 (0) | 2021.06.30 |
| [프로그래머스 | 파이썬] 기능개발- 큐사용 (0) | 2021.06.29 |
| [프로그래머스 | 파이썬] BFS와 DFS (4)/ 타겟넘버, 네트워크 (0) | 2021.06.29 |