이진 탐색

특정 값을 찾기 위해 앞에서부터 모든 값을 확인하는 순차 탐색과 달리, 이진 탐색은 탐색 범위를 절반씩 좁혀가며 탐색하는 빠른 알고리즘이다. 순차 탐색의 시간 복잡도는 O(N)이고 이진 탐색의 시간 복잡도는 O(logN)이다.

 

이진 탐색은 데이터가 정렬되어 있어야만 사용할 수 있다.

탐색할 범위의 시작점, 끝점, 중간점을 설정하고, 찾으려는 값과 중간값을 비교하여 시작점, 끝점, 중간점을 업데이트하는 과정을 반복한다.

 

반복되는 과정은 재귀함수나 반복문을 통해 구현할 수 있다.

# 재귀 함수 사용

def binary_search(array, target, start, end):
	if start > end:
    	return None		# None: 파이썬의 Null
    mid = (start + end) // 2
    
    if array[mid] == target:
    	return mid
    elif array[mid] > target:
    	return binary_search(array, target, start, mid-1)
    else:
    	return binary_search(array, target, mid+1, end)

# 반복문 사용

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

 

이진 탐색은 코딩테스트에 자주 출제된다고 하니 위의 코드는 외워 놓는 것이 좋겠다. 

 

트리 자료구조 중 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 항상 성립하는 트리를 이진 탐색 트리라고 한다. 이진 탐색 트리에서 값을 찾을 때는 루트 노드부터 왼쪽 혹은 오른쪽 자식 노드로 이동하며 찾으면 된다.

---

다음은 백준 단계별로 풀어보기 - 이분 탐색 파트의 문제들이다.