코딩테스트_이진탐색

binary_searchs.py

def binary_search(arr, start, end, val):
    if start > end:
        return -1
    mid = (start + end) // 2
    if arr[mid] == val:
        return mid
    elif arr[mid] > val:
        return binary_search(arr, start, mid - 1, val)
    elif arr[mid] < val:
        return binary_search(arr, mid + 1, end, val)

# 성능적으로 개선된 재귀호출을 사용하지 않는 이진탐색
def binary_search_non_recursive(arr, star, end, val):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == val:
            return mid
        if arr[mid] > val:
            end = mid -1
        elif arr[mid] < val:
            start = mid + 1
    return -1