이진탐색

 흔히 우리가 탐색을 할 때, 모든 배열을 확인하는 방법을 지양한다. 예를 들어 100까지 수 중에서 하나를 골라 up/down 게임을 한다고 하자. 우리는 보통 중간부터 수를 불러 좁혀나가는 식으로 하는 것이 빠르다는 것을 알고 있다. 따라서 모든 배열을 탐색하는 배열의 길이만큼의 시간 복잡도 대신 log2n의 시간복잡도를 갖을 수 있다. 

 이를 코드로 구현해보자!

# 이진 탐색 - 정렬이 되어있는 배열에서 가능
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_binary(target, array):
    current_min_idx = 0
    current_max_idx = len(array) - 1

    while current_min_idx < current_max_idx:
        current_avg_idx = (current_min_idx + current_max_idx) // 2
        if array[current_avg_idx] == target:
            return True
        elif array[current_avg_idx] > target:
            current_max_idx = current_avg_idx - 1
        elif array[current_avg_idx] < target:
            current_min_idx = current_avg_idx + 1

    return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

물론 이와 같은 updown 게임은 주어진 배열이 정렬이 되어 있어야한다는 전제 조건이 깔린다. 

 먼저, 배열이 시작과 끝을 각 변수의 넣어주고 해당하는 값으로 중간 값을 얻을 수 있다. 우리는 중간값과 타겟하는 값을 비교하면서 작은지 큰지에 따라 처음 지정해주었던 시작값과 끝 값을 변경할 수 있다.