[알고리즘] - 이분 탐색

이분 탐색 (Binary Search)

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
• 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행한다.
• 이분 탐색을 하기 위해서는 자료가 정렬된 상태여야 한다.
• 탐색 과정
  • 자료의 중앙에 있는 원소를 고른다.
  • 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
  • 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 절반에 대해서 새로 탐색을 수행하고, 크다면 자료의 오른쪽 절반에 대해서 새로 탐색을 수행한다.
  • 찾고자 하는 값을 찾을 때까지 위 과정을 반복한다.

예시

이분 탐색으로 20을 찾는 경우

코드로 구현

lst = [2, 4, 7, 8, 11, 19, 20, 23]
key = 20
start = 0
end = len(lst) - 1

while start <= end:
    mid = (start + end) // 2
    if lst[mid] == key:
        print(mid)
        break
    elif lst[mid] < key:
        start = mid + 1
    else:
        end = mid -1

# 함수로 구현
def binarySearch(arr, N, key): # arr = 배열, N = arr의 길이, key = 찾으려는 값
    start = 0
    end = N - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == key:
            return True		# 검색 성공
        elif arr[mid] < key:
            start = mid + 1
        else:
            end = mid - 1
    return False		# 검색 실패

+재귀 함수 이용

def binarySearch(arr, start, end, key):
    if start > end:
        return False
    else:
        mid = (start + end) // 2
        if arr[mid] == key:
            return True		# 검색 성공
        elif arr[mid] < key:
            return binarySearch(arr, mid+1, end, key)
        else:
            return binarySearch(arr, start, mid-1, key)