알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 이진 탐색

05-3 이진 탐색

- 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘

- 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음

- 시간복잡도: O(logN)

 

이진 탐색의 핵심 이론

이진 탐색 과정(오름차순 기준)

1. 현재 데이터셋의 중앙값을 선택한다.

2. 중앙값 > 타겟 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.

3. 중앙값 < 타겟 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.

4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

오름차순 정렬돼 있을 때

구현

# 재귀 활용
def binary_search(target, start, end):
	if start > end:
    	return -1
    
    mid = (start + end) // 2
    
    if data[mid] == target:
    	return mid
        
    elif data[mid] > target:
    	end = mid - 1
    
    elif data[mid] < target:
    	start = mid + 1
   
   return binary_search(target, start, end)
 
def solution(target, data):
	data.sort()
    start = 0
    end = len(data) - 1
    return binary_search(target, start, end)

참고 사이트