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

1. 이분탐색이란?

이분탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

이분탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이분탐색의 과정이다.

 

2. 이분탐색의 시간복잡도

이분탐색의 시간복잡도는 O(logN)이다. 여기서 log는 log₂를 의미한다.

단계마다 탐색 범위를 반으로 나누는 것과 동일하므로 위 시간 복잡도를 가지게 된다.

예를 들어 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게 된다.

즉, 이분 탐색은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장한다.

 

3. 이분탐색 알고리즘의 구현

이분탐색을 구현하기 위해서는 반복문, 재귀 두 가지 방법을 사용할 수 있다.

 

1. 반복문 사용

def binary_search(target, data):
	start, end = 0, len(data) - 1
    
    while start <= end:
    	mid = (start + end) // 2
        
        if data[mid] == target: # target과 일치할 경우
        	return data[mid] # target을 반환
        elif data[mid] < target: # target보다 작을 경우
        	start = mid + 1 # 더 큰 값의 범위에서 탐색하기 위해 start = mid + 1로 할당
        else: # target보다 클 경우
        	end = mid - 1 # 더 작은 값의 범위에서 탐색하기 위해 end = mid - 1로 할당
        
        return None # 찾는 값 없으면 None을 반환

 

 

2. 재귀 사용

def binary_search(target, data, start, end):
	if start > end:
    	return None
        
    mid = (start + end) // 2
    
    if target == data[mid]: # target과 일치할 때
    	return data[mid] # target을 반환
    elif data[mid] < target: # target보다 작을 때
    	return binary_search(target, data, mid+1, end) # 더 작은 값의 범위에 대해 재귀 호출
    else: # target보다 클 때 
    	return binary_search(target, data, start, mid-1) # 더 큰 값의 범위에 대해 재귀 호출

 

위 글은 https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search, https://thingjin.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search-%ED%8C%8C%EC%9D%B4%EC%8D%AC를 참고하여 작성하였습니다.