Binary Search - 이진 탐색

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

• 탐색 대상의 중간의 임의의 값(인덱스)를 선택하여 찾고자 하는 값과 비교한다.
• 주어진 범위를 재설정하여 범위를 좁힌다.
• 정렬되어있는 대상에 한정하여 사용할 수 있다.

  

import sys
from random import randrange
from typing import Optional

input = sys.stdin.readline


def binary_search_recursive(
    lst: list[int], left: int, right: int, target: int
) -> Optional[int]:
    if not lst:
        return None

    mid = (left + right) // 2

    if lst[mid] == target:
        return mid
    elif lst[mid] > target:
        return binary_search_recursive(lst, left, mid - 1, target)
    else:
        return binary_search_recursive(lst, mid + 1, right, target)


def binary_search_iterative(
    lst: list[int], left: int, right: int, target: int
) -> Optional[int]:
    while lst:
        mid = (left + right) // 2

        if lst[mid] == target:
            return mid
        elif lst[mid] > target:
            right = mid - 1
        else:
            left = mid + 1


def binary_search_main():
    N = int(input())
    lst = sorted([randrange(1, 100) for _ in range(N)])
    target_idx = randrange(N)

    print("검색 대상 : {}, 타겟 : {}, 타겟 인덱스 : {}".format(lst, lst[target_idx], target_idx))

    ans = binary_search_recursive(lst, 0, len(lst) - 1, lst[target_idx])
    if ans:
        print("재귀적 이진 탐색 - 타겟 인덱스 : {}".format(ans))

    ans = binary_search_iterative(lst, 0, len(lst) - 1, lst[target_idx])
    if ans:
        print("순차 이진 탐색 - 타겟 인덱스 : {}".format(ans))


binary_search_main()

참고

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://www.geeksforgeeks.org/binary-search/