이진탐색 요약

이진탐색

• 이진탐색의 제일 큰 특징은 "정렬된 데이터"에서 탐색하는 것이다(오름차순). 이유는 이진탐색이 search하는 방식에서 드러난다.

ex) 1 2 3 4 5에서 4를 찾는다고 할 때, 제일 먼저 리스트의 가운데를 탐색한다. 목표인 4를 가운데값 3과 비교해서 크면 오른쪽, 작으면 왼쪽으로 탐색을 이어간다. 이처럼 값의 크기에 따라 "왼쪽", "오른쪽"과 같이 방향을 가져야하므로 반드시 정렬이 된 상태로 탐색이 진행되어야한다.

• 가운데값을 보고 계속 탐색 범위를 반씩 줄여가므로 시간 복잡도는 O(log N)이 된다.

구현

재귀, 반복문 2가지 방법으로 구현이 가능하다. 공통점은 무조건 정렬하고 시작해야한다는 것 !!

반복문으로 구현

data = [4,2,3,7,1,9,6]
data.sort()

def binary_search(target, data):
    start = 0 # 시작 인덱스
    end = len(data) - 1 # 마지막 인덱스

    while start <= end: # start 인덱스가 end보다 크다면, 즉 start가 end보다 오른쪽에 있다면 종료
        mid = (start + end) // 2 # 매번 중간값을 탐색

        if data[mid] == target:
            return mid 		# target 위치 반환

        elif data[mid] > target: # target이 작으면 왼쪽을 더 탐색
            end = mid - 1
        else:                    # target이 크면 오른쪽을 더 탐색
            start = mid + 1
    return -1 # while 끝났는데도 return이 안됐다는 것은 못찾았다는 뜻이므로 -1 리턴

 

재귀로 구현

data = [9,4,6,7,1,2]
data.sort()

def binary_search(start, end, target):
    if start > end: # 탈출조건 : start가 end보다 오른쪽에 있는 경우
        return -1

    mid = (start + end) // 2 # 중간값

    if data[mid] == target:	# 중간값의 데이터가 target과 같다면 mid를 반환
        return mid

    elif data[mid] > target: # target이 작으면 왼쪽 탐색
        end = mid - 1
    else: # target이 크면 오른쪽 탐색
        start = mid + 1

    return binary_search(start, end, target) # 줄어든 범위를 더 탐색

print(binary_search(0, len(data)-1, 2)) # 2를 찾기 : 인덱스 1 반환