이진 탐색

이진 탐색

이진 탐색은 정렬된 배열에서 중간값을 기준으로 절반씩 나눠가며 탐색하는 기법으로, $O(\log_2 n)$의 시간 복잡도를 가집니다. 이진 탐색은 정렬된 배열에서만 사용 가능하고, 반복문과 재귀함수로 구현할 수 있습니다.

위와 같은 배열에서 이진 탐색을 사용하여 7 이라는 값을 찾는다고 하면, 먼저 중간 값인 5를 탐색합니다. 이때 중간값의 인덱스는 $\displaystyle\frac{start + end}{2}$입니다. 처음의 start와 end 는 0, 4 이므로, 중간 인덱스는 2입니다. 이때 탐색하려는 키가 5보다 크므로, 오른쪽 부분을 탐색합니다.

이때도 중간값을 탐색합니다. $\displaystyle\frac{3+4}{2}=3.5$이므로, 정수부분인 3번 인덱스를 탐색합니다. 이때 값이 키와 같으므로 탐색을 종료합니다.

그러나 만약 배열에 포함되지 않는 값을 탐색한다면 어떻게 될까요? 위의 배열에서 10이라는 값을 찾아보겠습니다. 위와 같은 방법으로 마지막 인덱스인 9 까지 탐색할 수 있습니다. 이때 start 와 end가 4로 같습니다. 다음번 탐색을 할 때는 key < value 이기 때문에 중간 인덱스보다 오른쪽의 값을 탐색하게 되므로, start + 1을 해줘야합니다. 그러나 이렇게 되면 start > end가 되기 때문에 탐색이 불가합니다. 따라서 start > end인 경우 탈출하는 조건이 필요합니다.

Python 코드

def binary_search_recursive(target, start, end): # 재귀 구현
    mid = (start + end) // 2
    if arr[mid] == target:
        return True
      # return mid <- 인덱스 반환

    if start > end:
        return False
      # return -1 <- 만약 존재하지 않는다면, -1

    if arr[mid] > target:
        return binary_search_recursive(target, start, mid - 1)
    else:
        return binary_search_recursive(target, mid + 1, end)

def binary_search_loop(target, start, end): # 반복문 구현
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return True
          # return mid <- 인덱스 반환
        if arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return False
  # return -1 <- 만약 존재하지 않는다면, -1