[Algorithm]이진 탐색(Binary Search)

✏️ 이진 탐색이란?

  이진 탐색(binary search)란 정렬된 데이터에서 특정한 값을 찾아내는 방법이다. 전체를 절반으로 구분해서 현재 자기 위치가 찾는 위치보다 값이 큰지 작은지에 따라 탐색 방향을 결정하는데, 핵심은 필요 없는 부분을 탐색하지 않는 것이다.

  정렬된 데이터는 일정한 순서로 나열되어 있기 때문에 찾는 위치가 지금 위치보다 뒤에 있다면 그보다 앞의 데이터는 찾아보지 않아도 상관이 없다. 따라서 중앙에서부터 값을 비교하기 시작해서 매 탐색마다 탐색 범위가 절반씩 줄어든다.

  이진 탐색의 가장 큰 장점은 데이터가 정렬되어 있다면 시간복잡도가 $O(logn)$로 줄어든다는 점이다. 따라서 문제에서 주어지는 입력의 크기가 크다면 이진 탐색을 사용하는 것이 좋다.

✍🏻 구현 방법

def binarySearch(data, target):
    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 -1 # 탐색에 실패하면 -1 반환

my_list = [1, 2, 3, 7, 9, 11, 33]
print(binarySearch(my_list, 3))
>>> 2

✍🏻 파라메트릭 서치(parametric search)

  파라메트릭 서치란 정렬 없이 이진 탐색 개념만 사용해 문제를 푸는 것이다. 현재의 상황에서 어떻게 나아갈 것인지를 판단하는 방식으로 이진 탐색을 응용하는 방법이다.

  파라메트릭 서치는 매개변수를 사용하여 예/아니오 방식처럼 두 갈래로 나눠 탐색하는 방법을 의미한다. 선택지가 결정되었을 때 실행할 기능을 함수로 만든 뒤, 선택지를 함수의 매개변수로 제공하여 그 값에 따라 탐색 방향을 결정하는 것이다. 다만, 주어진 기준에서 최댓값/최솟값을 구할 수 있어야 하고 정렬 형태(1번 조건을 만족하면 그보다 작은 값, 큰 값도 1번 조건을 만족해야 함)로 구성되어야 한다.

---

© 참고
https://cjh5414.github.io/binary-search/
https://code-angie.tistory.com/3