정렬되어 있는 리스트에 대해 효과적인 탐색
시작, 중간, 끝 정보를 이용해 탐색 범위를 반에 가깝게 줄여나가자.

이진 탐색 Binary Search

Divide and Conquer?

매 단계마다 탐색 범위를 반으로 줄이기.
약간 분할 정복 느낌????

시작, 중간, 끝 정보를 이용해 탐색 범위를 줄이자.
중간값과 찾는 값의 대소비교를 통해 탐색 방향을 정하자.

이진 탐색을 위한 전제 조건은 iterable이 정렬되어 있어야 한다는 것.
정렬되지 않은 iterable을 반으로 쪼개봤자 의미가 없지 않을까?

재귀 or 반복문을 통해 각각 구현이 가능한데...해결하고자 하는 문제에 따라 맞춰 구현하면 된당..

핵심 로직

1. 기저조건
2. 중간 인덱스 구하기
3. 중간값과 찾는 값 비교를 통해 이진 분할 방향 결정

단계를 찾는 값을 찾거나, 기저조건에 전체 탐색이 종료될때까지 반복한다ㅏㅏㅏㅏ.

매 단계를 거칠 때마다 탐색범위는 절반가량 줄어들게 된다!
                               log2N!
따라서 이진탐색의 시간복잡도는 O(logN)

구현

재귀로 구현하기

def binary_search(array, value, left, right):
	if left > right:
    	return
    mid = (left + right) // 2
    if array[mid] == value:
    	return mid
    elif array[mid] > value:
    	return binary_search(array, value, left, mid-1)
    else:
    	return binary_searh(array, value, mid+1, right)

반복문으로 구현하기

def binary_search(array, value, left, right):
	while left <= right:
   		mid = (left + right) // 2
		if array[mid] == value:
        		return mid
		elif array[mid] > value:
        		right = mid -1
		else:
        		left = mid + 1
	return None

더보기

bisect

이진 탐색 트리

FINDSTUFF

TTEOKBOKKI (Feat.파라메트릭 서치)

‹ 탐색 알고리즘 목록으로