[기술면접/알고리즘] Binary Search (이진 탐색)

Binary Search (이진 탐색)에 대해 설명하세요

Keyword

정렬된 배열, 하한값, 상한값, 중간값

Script

이진 탐색은 정렬된 배열에서 특정한 값을 빠르게 찾아내는 알고리즘입니다. 매번 하한값과 상한값 사이의 중간값에 접근하여, 목표하는 값과의 비교를 통해 하한과 상한의 격차를 줄여나가며, O(logN)의 시간복잡도로 탐색을 수행할 수 있습니다.

Additional

코드 (python)

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None