Binary Search (이진 탐색)

이재상·2021년 2월 15일
0

algorithm

목록 보기
2/2
post-thumbnail

Binary Search란?

자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 진행하는 방법입니다.

목적 값을 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행하는 탐색 방법으로써 주의해야 될 사항은 이진 검색을 하기 위해서는 자료의 형태가 정렬된 상태여야 합니다.

검색 과정

  • 자료의 중앙에 있는 원소를 고른다.
  • 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
  • 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반(half)에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반(half)에 대해서 새로 검색을 수행한다.

시간 복잡도

  • O(logn)


    이진 탐색을 구현하는 방법을 두 가지로 작성해 보겠습니다.

구현

  • 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다.
  • 이진 탐색의 경우, 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.
def binarySearch(a, key):
    start = 0
    end = len(a)-1
    while start <= end:
        middle = (start + end)//2
        if a[middle] == key :		# 검색 성공
        	return True
       	elif a[middle] > key:
            end = middle -1
        else: start = middle + 1
    return False		# 검색 실패

다음은 재귀 호출 방법으로 이진 탐색을 구현해 보겠습니다.

def binaryRecursive(a, low, high, key) :	#재귀호출
	if high < low : # 검색 실패, 재귀 탈출
    	    return False
   	else:
            middle = (low + high) // 2
            if key == a[middle]: 	#검색 성공
                return Ture
            elif key < a[middle] :
                return binarySearch2(a, low, middle-1, key)
            elif a[middle] < key:
                return binarySearch2(a, middle+1, high, key)

정리

이진 탐색은 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있습니다. 하지만 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 정렬되어 있는 경우 순차 탐색(Sequential Search)보다 속도가 빠를 수 있다는 장점이 있어 여러모로 편리한 방법인 것 같습니다.

profile
차근차근 공부한 것을 정리하는 곳

0개의 댓글