이진 탐색

이진 탐색의 정의

이진탐색은 찾는 값이 있는 리스트의 중간에 있는 값과 찾으려는 값을 반복적으로 비교하여 탐색하는 알고리즘이다.
따라서 찾는 값이 있는 리스트가 정렬이 되어 있어야만 사용할 수 있다.

이진 탐색 예시

다음과 같은 리스트가 있다고 하고, 우리가 찾고싶은 값이 12라고 하자.
1. 리스트의 중간 인덱스의 값을 찾아보면 [0]과 [7] 의 중간인 [3]이고, 해당하는 값은 2이다.(.5가 나오게 되면 절사)
2. 2보다 12가 크므로 [3]을 포함한 [0],[1],[2],[3] 안에는 찾고싶은 값이 없으므로 버린다.
3. [4]부터[7]까지에서 이진탐색을 진행한다. [5]의 값인 10보다 12가 크므로 [5]이하의 값을 버린다.
4. [6],[7]에서 [6]의 값이 12로 찾고싶은 값과 같으므로 중단한다.

이진 탐색의 빅오 표기

위와 같이 절반을 버리고 진행을 하므로 연산 횟수는 log2n과 비례한다.
따라서 이진 탐색은 O(logn)라고 빅오 표기를 할 수 있다.

이진 탐색 구현

이진 탐색은 같은 일을 계속 반복하므로 일반적으로 재귀, 반복문 이렇게 두가지 구현법을 생각해볼 수 있다.

# 재귀로 구현한 이진탐색 
def binary_search(list, target, start, end):
	if start > end:
    	return None
    mid = (start + end) // 2 
    if list[mid] == target:
    	return mid
    elif list[mid] > target:
    	return binary_search(list, target, start, mid-1)
    elif list[mid] < target:
    	return binary_search(list, target, mid+1, end)

# 반복문으로 구현한 이진탐색
def binary_search(list, target, start, end):
	while start <=end:
    	mid = (start + end) // 2
        if list[mid] == target:
        	return mid
        elif list[mid] > target:
        	end = mid-1
        elif list[mid] < target:
        	start = mid+1
     return None

언제 이진탐색을 사용하지?

탐색 범위가 매우 큰 경우 이진 탐색을 사용하는 경우가 많다. O(logn)이기 때문에.

이진탐색 트리

이진 탐색 트리의 정의

이진 탐색이 동작할 수 있도록 고안된 자료구조.
다음과 같은 특징을 가진다.

• 부모노드보다 왼쪽 자식 노드가 작다.
• 부모노드모다 오른쪽 자식 노드가 크다.

이진 탐색 트리의 활용

기본적인 개념은 이진탐색 알고리즘과 같다.
루트노드부터 값을 비교해나가며 기준보다 작으면 왼쪽, 크면 오른쪽으로 간다.
리프노드에서도 찾지 못하면 해당 트리에 찾고싶은 값이 없는 것이다.