[Python] 이진 검색(Binary Search)

이진검색

(1) 정의

- 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법으로,

목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여나가며 보다 빠르게 검색을 수행하는 방법입니다.

 

- 이진검색을 하기 위해서는 자료가 정렬된 상태여야 합니다.

 

- 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)보다 빠르게 데이터 탐색이 가능합니다.

 

(2) 검색 과정

 

① 자료의 중앙에 있는 원소를 고릅니다.

② 중앙 원소의 값과 찾고자 하는 목표 값을 비교합니다.

③ 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고,

크다면 오른쪽 반에 대해서 새로 검색을 수행합니다.

④ 찾고자 하는 값을 찾을 때까지 ① ~③  을 반복합니다.

 

(예시)

* 이진 검색으로 20을 찾는 경우

①  중앙의 값을 찾았을때 20 (찾을 값) > 9 (중앙 값) 이므로 오른쪽을 검색합니다.

② 20 > 19 이므로 오른쪽을 검색합니다.

③ 남은 값인 23은 찾을 값인 20과 다르므로 검색 실패가 됩니다.

 

(3) 알고리즘 : 반복구조

binarySearch(n, S[], key)
low <- 0
high <- n-1

WHILE low <= high
	mid <- low + (high - low) / 2
    
    IF S[mid] == key
    	RETURN mid
    ELIF S[mid] > key
    	high <- mid - 1
    ELSE 
    	low <- mid + 1
RETURN -1

 

(4) 알고리즘 : 재귀구조

binarySearch(a[], low, high, key)
	IF low > high
    	RETURN -1
    ELSE
    	mid <- (low + high) / 2
        IF key == a[mid]
        	RETURN mid
        ELIF key < a[mid]
        	RETURN binarySearch(a[], low, mid - 1, key)
        ELSE
        	RETURN binarySearch(a[], mid + 1, high, key)

 

 

 

(5) 관련 알고리즘