[Python3] 이진탐색 알고리즘 반복문, 재귀

 

이미 정렬되어 있을때 사용

시간복잡도 O(logN)

 

반복문

def binary(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid-1
        else:
            start = mid+1
    return None

 

재귀

 

def binary(array, target, start, end):
    if start>end:
        return None
    mid = (start+end) // 2

    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary(array, target, start, mid-1)
    else:
        return binary(array, target, mid+1, end)