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

이분 탐색 / 이진 탐색이란,

오름차순으로 정렬된 리스트에서 검색 범위를 좁히면서 특정한 값을 검색하는 알고리즘이다.

---

💡알고리즘 원리💡

간단하게 설명하면 중앙값을 기준으로 찾고자 하는 값과 비교하며 검색의 범위를 좁혀나가는 것이다. 그래서 기존의 순차적으로 검색하는 방식과 비교하였을 때 처리 속도가 빠르다는 장점을 가진다.

🔗동작 과정

1. 중앙값 초기화
2. 중앙값과 검색값 비교
   1) 중앙값 $=$ 검색값이면, 탐색 종료
   2) 중앙값 $\neq$ 검색값이면, 탐색 범위 감소

   • 중앙값 < 검색값, 검색범위: 중앙값 ~ 최댓값
   • 중앙값 > 검색값, 검색범위: 최솟값 ~ 중앙값

3. 값을 찾거나 탐색 범위가 없을 때까지 반복
   
   

👀예제와 함께 살펴보기

$[1, 3, 5, 7,11,13,17,19,23,31,37,41,43,47,53,59]$의 오름차순으로 정렬된 리스트에서 $37$의 위치를 찾고자 한다.

순차적으로 찾는 방식은 $37$을 찾기 위해서는 11번의 탐색과정이 필요하다.
그러나, 이분 탐색 알고리즘은 3번의 탐색과정만으로도 37을 찾을 수 있다.

이분 탐색 알고리즘에서 탐색은 인덱스를 기준으로 한다.

1. min = 0, max = 16 ▶ mid = (0 + 16)//2 = 8
   최솟값 0, 최댓값 16으로 중앙값을 계산한다.
   중앙값이 23으로 검색값 보다 작기 때문에
   탐색 범위를 중앙값 이후인 $[29,31,37,41,43,47,53,59]$로 좁힌다.
   

2. min = 9, max = 16 ▶ mid = (9 + 16)//2 = 12
   최솟값 9, 최댓값 16으로 중앙값을 계산한다.
   중앙값이 41로 검색값 보다 크기 때문에
   탐색 범위를 중앙값 이전인 $[29,31,37]$로 좁힌다.
   

3. min = 9, max = 11 ▶ mid = (9 + 11)//2 = 10
   최솟값 9, 최댓값 11으로 중앙값을 계산한다.
   중앙값이 31로 검색값 보다 작기 때문에
   탐색 범위를 중앙값 이후인 $[37]$로 좁힌다.
   

4. min = 11, max = 11 ▶ mid = (11 + 11)//2 = 11
   최솟값 11, 최댓값 11으로 중앙값을 계산한다.
   중앙값이 37로 검색값과 같아 탐색이 종료된다.
   37의 위치는 11이다.
   

---

🔎알고리즘 특징🔎

🔘 오름차순으로 정렬되어 있는 리스트에만 적용이 가능하다.

🔘 검색 과정마다 탐색범위가 반으로 감소하기 때문에 처리속도가 빠르다.

🔘 데이터 양이 많아도 적용이 쉽다.

⏰시간 복잡도

시간 복잡도란,

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 나타내는 지표로,
주로 계수와 낮은 차수의 항을 제외시키는 빅-오 표기법을 사용한다.

알고리즘	Best	Worst
선형 탐색	$O(1)$	$O(N)$
이분 탐색	$O(1)$	$O(log N)$

---

💻코드 구현💻

반복문으로 구현하기

# key는 찾고자 하는 값, arr은 정렬된 리스트
def binary_search(key, arr):
	min_v, max_v = 0, len(arr)-1 # 최솟값과 최댓값
    
    # 종료조건 - 탐색범위 없음
    while min_v <= end:
    	mid = (min_v + max_v) // 2
        
        if arr[mid] == key: 
        	return mid		# 종료조건 - 탐색값 발견
        elif arr[mid] > key:
        	max_v = mid-1	# 최댓값 갱신
        else:
        	min_v = mid+1	# 최솟값 갱신
            
	return -1 # 탐색 실패

재귀로 구현하기

# key는 찾고자 하는 값, arr은 정렬된 리스트
def binary_search(key, arr, min_v, max_v):
	if min_v > end_v:	# 종료조건 - 탐색범위 없음
    	return -1
        
    mid = (min_v + max_v) // 2
    if arr[mid] == key: 
        return mid		# 종료조건 - 탐색값 발견
    elif arr[mid] > key:
       	return binary_seach(key, arr, min_v, mid-1)	# 최댓값 갱신
    else:
       	return binary_seach(key, arr, mid+1, max_v)	# 최솟값 갱신