몇 분 안에 이진 검색

다음 배열에서 요소 38의 위치를 ​​찾고 싶다고 가정해 보겠습니다.

먼저 배열의 중간점을 찾습니다. mid = (low + high)/2 공식을 사용하여 중간점을 찾을 수 있습니다.

38을 중간 요소와 비교하십시오. 25는 38보다 작기 때문에 전반부는 생략합니다. 후반부의 경우 낮음 = 중간 + 1입니다.

대상 요소의 중간 지점까지 반복하고 인덱스(이 경우 6)를 반환합니다.

# iterative approach
def iterative_binary_search(list, target):
    low = 0
    high = len(list) - 1

    while high > low:
        mid = math.floor((low + high) / 2)
        if list[mid] == target:
            return mid
        elif list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# recursive approach
def recursive_binary_search(list, target, low, high):
    if low < high:
        mid = math.floor((low + high) / 2)

        if list[mid] == target:
            return mid
        elif list[mid] < target:
            return recursive_binary_search(list, target, mid + 1, high)
        else:
             return recursive_binary_search(list, target, low, mid - 1)

    return -1