이진탐색(binary search)란 무엇인가? (python)

목차

I. 이진 탐색 정의

II. 이진 탐색을 사용하는 이유

III. 이진 탐색 구현

 

I. 이진 탐색의 정의

이진 탐색은 '이미 정렬되어 있는 배열'에서 효율적으로 원하는 값을 탐색하는 알고리즘이다

 

이진 탐색은 이름에서 유추할 수 있듯, 동작 방식이 매우 간단하다.

다음과 같은 배열이 존재하며, 19를 찾는 상황이라고 가정해보자

 

 

배열의 중앙 값을 찾은 뒤 찾고자하는 값보다 작다면 오른쪽 배열의 중앙 값을 또다시 찾아본다

위 과정을 반복하여, 찾고자하는 값(19)를 찾아낸다

 

 

 

II. 이진 탐색을 사용하는 이유

위 동작을 통해서 유추가 가능하겠지만, 반복문이 진행될 때마다, 탐색해야 할 배열의 원소가 절반으로 줄어들기 때문에 시간 복잡도가 O(log n)으로 탐색이 매우 빠르다

 

 

 

III. 이진 탐색 구현 방법

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

 

배열, 목표값, 시작 지점, 끝 지점을 parameter로 지정합니다.

start 지점이 end랑 같거나 커지는 순간 종료됩니다

 

반복문이 진행되는 동안, mid = (start + end) // 2로 새로 할당을 진행하게 되며

찾고자하는 값이 배열의 가운데 지점과 일치하면 반환합니다

만약, 배열의 중앙 값이 목표 값보다 크다면, 배열의 왼쪽 부분을 탐색해야하기 때문에 end = mid - 1로 지정합니다.

반대의 경우 start = mid + 1로 지정합니다

 

탐색 결과, 값을 찾지 못했을 경우 None을 반환합니다