이분 탐색

이진 탐색

특정 값을 찾기 위해 앞에서부터 모든 값을 확인하는 순차 탐색과 달리, 이진 탐색은 탐색 범위를 절반씩 좁혀가며 탐색하는 빠른 알고리즘이다. 순차 탐색의 시간 복잡도는 O(N)이고 이진 탐색의 시간 복잡도는 O(logN)이다. 이진 탐색은 데이터가 정렬되어 있어야만 사용할 수 있다. 탐색할 범위의 시작점, 끝점, 중간점을 설정하고, 찾으려는 값과 중간값을 비교하여 시작점, 끝점, 중간점을 업데이트하는 과정을 반복한다. 반복되는 과정은 재귀함수나 반복문을 통해 구현할 수 있다. # 재귀 함수 사용 def binary_search(array, target, start, end): if start > end: return None# None: 파이썬의 Null mid = (start + end) // 2 if..