코테대비 01. 이진 탐색 (Binary Search)

원리

배열 A가 정렬되어 있다고 할 때,

• A の真ん中の要素が k 未満であれば、A の前半分の要素もすべて k 未満であることがわかります。つまり、A の前半分について探索する必要が無くなります。

A의 중앙값보다 비교할 요소가 작다면, 나머지 오른쪽 절반의 요소들 보다 작다.

• 逆に、A の真ん中の要素が k より大きければ、A の後ろ半分の要素もすべて k より大きいので、A の後ろ半分について探索する必要が無くなります。

A의 중앙값보다 비교할 요소가 크다면, 나머지 왼쪽 절반의 요소들 보다 크다.

• つまり、「対象とする探索範囲の中央の値」と「探索したい値」を比較することで、探索範囲を半分にすることができます。

즉, 탐색 범위의 중앙 값과 탐색하고 싶은 값을 비교하며 탐색 범위를 절반으로 줄일 수 있다!

---

Tip

• ソート済みであること

정렬되어 있어야 한다.

• 二分探索をおこなう際は、区間をどのような形で持つか (開・閉・半開) を問題に合わせて適切に選択する必要があります。

문제에 따라 비교 범위의 개구간 폐구간을 신경써야 한다.

---

Sudo 코드

/**
ソート済みの数列 A に 値 k が含まれているなら true を、含まれていないなら no を返す
*/
binary_search(A : 数列, n : 数列のサイズ, k : 探索する値)
    // 探索範囲 [left, right]
    left = 0
    right = n-1
    
    // 探索範囲を狭めていく
    while left <= right

        // 探索範囲の中央
        mid = (left + right) / 2

        if A[mid] == k then
            return true
        else if A[mid] < k then
            left = mid+1
        else 
            right = mid-1
    
    return false

static bool BinarySearch(List<int> sortedList, int target)
    {
        int low = 0;
        int high = sortedList.Count - 1;

        while (low <= high)
        {
            int mid = (low + high) / 2;

            if (sortedList[mid] == target)
                return true;
            else if (sortedList[mid] > target)
                high = mid - 1;
            else
                low = mid + 1;
        }

        return false;
    }

---

시간 복잡도

O(log N)

---

예제

https://paiza.jp/works/mondai/binary_search/binary_search__basic_step0/edit?language_uid=c-sharp&t=13e37cdf77b52361e66b52b7de9a0fbb

ログイン

 

https://machineboy0.tistory.com/323

Excercism - Binary Search : 이진탐색, 이진탐색 트리