이진 탐색

이진 탐색

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이는 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다.

• 시작점과 끝점을 확인한 후에 중간점을 정한다. step1 에서는 중간점이 target인 4 보다 크기 때문에 끝점을 중간점 - 1로 조율한다.
• step2 에서는 중간점보다 target의 값이 더 크므로 시작점 = 중간점 + 1 로 조율한다.
• 중간점과 target 이 동일하므로 탐색을 종료한다.
• 매번 탐색할 때 마다 탐색의 범위가 절반씩 줄어든다는 점에서 시간복잡도는 O(logN) 이다.

소스코드

이진 탐색은 재귀 방식과 반복문 2가지 형식으로 구현할 수 있다.

재귀

#탐색 배열, 찾고자 하는 값, 시작점, 끝점
def binary_search(array, target, start, end):
    if start > end:
        return None
    
    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)
    
#원소의 개수, 찾고자하는 값
n, target = 10, 7
#전체 원소
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

result = binary_search(array, target, 0, n - 1)
if result == None:
    print('찾고자하는 원소 존재 X')
else:
    #실행결과: 4 번째 위치
    print(result + 1, '번째 위치')

반복문

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

#생략

탐색 범위가 2000만을 넘어가거나, 처리해야할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면 이진 탐색을 사용하도록 하자.