[알고리즘/Python] 이진/이분 탐색 (Binary Search)

1. 이진 탐색(Binary Search) 이란?

탐색 범위를 반으로 줄여가며 데이터를 찾는 알고리즘

정렬된 배열에서 특정한 값을 효율적으로 찾는 탐색 알고리즘이다.
이진 탐색은 배열에서의 값 탐색, 범위 내의 특정 조건을 만족하는 요소 찾기(예: 최소 또는 최대 값의 경계 찾기), 알고리즘 문제 해결 시 탐색 범위를 좁혀나가는 과정 등의 다양한 상황에서 활용할 수 있다.

• 이진 탐색을 수행하기 전에 데이터가 정렬되어 있어야 한다.
• 탐색 범위 내에서 중간 위치의 요소를 선택한다.
• 중간점의 데이터와 찾고자 하는 값(target)을 비교한다.
  • 중간점의 데이터가 찾고자 하는 값과 일치 : 탐색 종료
  • 중간점의 데이터가 찾고자 하는 값보다 작을 때 : 탐색 범위의 왼쪽 부분을 버리고 오른쪽 부분을 새로운 탐색 범위로 설정
  • 중간점의 데이터가 찾고자 하는 값보다 클 때 : 탐색 범위의 오른쪽 부분을 버리고 왼쪽 부분을 새로운 탐색 범위로 설정
• 새로운 탐색 범위를 기반으로 위의 과정을 target 값이 발견되거나 탐색 범위가 더 이상 존재하지 않을 때까지 반복 수행한다.

2. Time Complexity

이진 탐색의 시간복잡도는 O(logN)이다.

이진 탐색을 반복할수록 남아 있는 요소의 개수는 1/2로 줄어든다.

• 1번째 수행시 탐색할 남은 요소의 개수 : $N$
• 2번째 수행시 탐색할 남은 요소의 개수 : $N/2$
• 3번째 수행시 탐색할 남은 요소의 개수 : $N/2 * 1/2$
• 4번째 수행시 탐색할 남은 요소의 개수 : $N/2 * 1/2 * 1/2$

이런 식으로 반복되는데, K번째 수행하게 되면 남은 자료의 개수는 $N * (1/2)^K$ 로, 탐색이 끝나는 시점에는 남은 자료의 개수가 1이 되어야 한다.

즉, $N * (1/2)^K = 1$의 방정식을 세울 수 있다.
양변에 $2^K$를 곱하면, $2^K = N > K = log2^N$ 으로, N에 따른 시행횟수는 $log2^N$이다.

3. 구현

(1) 반복문

def binary_search_iterative(arr, target):
	left, right = 0, len(arr) - 1
    
    while left <= right:
    	mid = (left + right) // 2
    	if arr[mid] == target:
        	return True
        elif arr[mid] < target:
        	left = mid + 1
        else:
        	right = mid - 1
    return False

(2) 재귀

def binary_search_recursive(arr, target, left, right):
	if left > right:
    	return False
    
    mid = (left + right) // 2
    if arr[mid] == target:
    	return True
    elif arr[mid] < target:
   		return binary_search_recursive(arr, target, mid + 1, right)
    else:
    	return binary_search_recursive(arr, target, left, mid - 1)

---

Reference

https://wikidocs.net/233716
https://www.mathwarehouse.com/programming/gifs/binary-vs-linear-search.php
https://jwoop.tistory.com/9