[알고리즘 종류] 이진 탐색 (Binary Search)

- 이진 탐색

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
• 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 함

def binary_search(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 binary_search(a, start, end, key):
    if start > end: # 검색 실패
        return False
    else:
        middle = (start + end)//2

        if a[middle]== key:
            return True # 검색 성공
        elif a[middle] > key:
            return binary_search(a, start, middle+1, key)
        else:
            return binary_search(a, middle-1, end, key)

 

📄 관련 문제

https://glory-summer.tistory.com/152

[프로그래머스] 입국심사 (이분탐색)