[Python] 이진 탐색 (Binary Search)
이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 정렬된 데이터에서 원하는 데이터를 빠르게 찾을 수 있다는 장점이 있다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용한다. 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색이다. 한번 확인할 때마다 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다. 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근하는 것을 고려해보면 좋다. 구현하는 방법에는 두가지가 있다. 1. 재귀 함수로 구현 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(ar..
