[Binary Search] 이진 탐색이란 무엇인가? 나누면서 탐색?

반으로 나누면서 원하는 값을 찾아가는 탐색방법 - 전제는 정렬

 

시작점 중간점 끝점이 제일 중요하다

• 중간점을 기준으로 찾으려는 값이 작으면 중간점 아래로 찾고
• 중간점을 기준으로 찾으려는 값이 크면 중간점 위로 찾는다

중간점과 찾으려는 값이 같으면 idx 토해내고

시작점이 끝점보다 더 커지는 순간이 온다면 찾지 못했다는 뜻이니 None을 반환

 

시작점이 왜 끝점보다 클때 그만?

요소가 한개인 경우에는 시작점과 끝점이 같다

한개인 경우에 그게 찾는 수가 아니라면 끝점이 -1 되거나 시작점이 +1 될 것이다

두 경우 모두다 시작점이 끝점을 초과시이므로 그 때 끝낸다

시간복잡도

절반으로 나누어지면서 찾아가기 때문에 트리 모양이다

O(logN)

재귀를 통해 푸는 방법

def binary_search(array, l, h, num):
    if l>h:
        return None
    mid = (l+h)//2
    if array[mid] == num:
        return mid
    if num > array[mid]:
        return binary_search(array, mid+1, h, num)
    else:
        return binary_search(array, l, mid-1, num)

무한루프를 통해 푸는 방법

def binary_search(array, l, h, num):
    start = l
    end = h
    while start<=end:
        mid = (start + end) //2
        if array[mid] == num:
            return mid
        if num > array[mid]:
            start = mid+1
        else:
            end = mid-1
    return None

print(binary_search(array, 0, len(array), 43))