[Algorithm] 이분 탐색(Binary Search)

이분 탐색에 대한 내용을 정리해보려고 합니다.

 

 

이분 탐색

 

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법입니다.

 

이분 탐색을 사용해야하는 이유 ?

우리가 일반적으로 알고있는 선형 탐색의 경우에는 앞에서부터 순차적으로 탐색하기 때문에 시간 복잡도는 배열의 원소의 개수 만큼(O(n))이 됩니다. 만약 원소의 개수가 무수히도 많아진다면 굉장히 비효율적인 알고리즘이 되겠죠.

하지만 이분 탐색은 탐색 범위를 절반으로 나누어서 탐색하기 때문에 시간 복잡도는 O(log n)로 탐색이 가능합니다.

 

 

이분 탐색 동작

 

 

이분 탐색의 동작을 알아보도록 하겠습니다.

 

예를 들어서 배열 arr = {1, 3, 5, 7, 9, 10, 13, 15} 에서 13을 찾아보도록 하겠습니다.

(여기서 배열은 반드시 정렬 되어 있어야 합니다.)

 

 

이분 탐색을 진행할 때 두개의 변수가 필요합니다.

변수 start와 end는 내가 찾고자하는 값(13)이 있을 수 있는 범위를 나타냅니다.

(이 범위 안에서 내가 찾고자하는 값이 없을 수도 있습니다.)

 

 

 

여기서 탐색 범위를 절반으로 줄이기 위한 하나의 변수가 필요합니다.

변수 mid는 start와 end의 절반의 지점을 나타냅니다. (start + end / 2)

(C++ 언어 특성상 start + end가 홀수라면 나머지는 버립니다.)

지금 start는 0, end는 7, mid는 3입니다.

 

arr[mid]이 찾고자하는 수(13)와 비교하여 범위를 나타내는 변수인 start 또는 end 값을 바꿀 것입니다.

비교해보면 arr[mid] = 7 인데 찾고자하는 값은 13이고 mid 이하의 인덱스에는 13이 없다는 사실을 알 수 있습니다.

그래서 범위를 start = mid + 1로 변경하여 탐색 범위를 절반으로 줄일 수 있습니다.

 

 

 

범위가 절반으로 줄었으므로 mid 또한 mid = (start + end) / 2로 계산합니다.

arr[mid] = 10은 13보다 작기 때문에 mid(5) 이하의 인덱스에는 13이 없다는 사실을 알 수 있습니다.

그래서 범위를 start = mid + 1로 변경하여 탐색 범위를 절반으로 줄일 수 있습니다.

 

 

범위가 또 절반으로 줄었으므로 mid 또한 (start + end) / 2로 계산합니다.

arr[mid] = 13은 내가 찾고자하는 값입니다.

 

 

만약 찾고자하는 값이 배열에서 있을 수도 없을 수도 있습니다.

그렇다면 내가 찾고자하는 값이 없다면 어떤 상황이 발생하는지 알아보겠습니다.

 

위 예시와 동일한 배열 arr = {1, 3, 5, 7, 9, 10, 13, 15}에서 값 6을 찾아보도록 하겠습니다.

 

start = 0, end = 7, mid = 3 입니다.

arr[mid] = 7이 찾고자하는 값 6보다 크기 때문에 end를 mid - 1로 변경합니다.

 

 

범위가 절반으로 줄었기 때문에 mid는 start + end / 2를 통해 1로 계산됩니다.

arr[mid] = 3은 찾고자하는 값 6보다 작기 때문에 start를 mid + 1로 변경합니다.

 

 

또 범위가 절반으로 줄었기 때문에 mid는 start + end / 2를 통해 2로 계산됩니다.

여기서 start, end, mid가 한곳에 모였습니다.

 

그리고 arr[mid] = 5는 찾고자하는 값 6보다 작기 때문에 start를 mid + 1로 변경합니다.

 

 

 

아래와 같이 start와 end가 역전되었습니다.

또한 6이 있을 수 있는 범위를 의미하는 start와 end 사이의 값 또한 사라졌습니다.

그렇기 때문에 배열 안에 6이 없음을 알 수 있습니다.

 

 

 

이분 탐색 구현

 

위 내용을 기반으로 이분 탐색을 구현한 내용입니다.

#include <bits/stdc++.h>
using namespace std;

int binarysearch(int target, vector<int>& arr) {
    int start = 0;
    int end = arr.size() - 1;
    while(start <= end) {
        int mid = (start + end) / 2;
        if(arr[mid] < target) {
            start = mid + 1;
        } else if(arr[mid] > target) {
            end = mid - 1;
        } else {
            return mid; // 찾았다면 찾은 인덱스를 반환한다.
        }
    }
    return -1; // 찾는 수 없음
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> arr = {1, 3, 5, 7, 9, 10, 13, 15};
    // 13이라는 수를 찾을 것이고 배열의 몇번째 인덱스에 있는지 위치를 반환한다.
    cout << binarysearch(13, arr) << '\n';
    // 찾는 수가 없다면 -1을 출력한다.
    cout << binarysearch(6, arr) << '\n';
}

 

 

 

STL 이분 탐색

 

 

물론 구현해보는 것도 좋지만, 친절한 C++은 STL에 binary_search 함수가 존재합니다.

➜ 범위를 주면 주어진 범위 내에서 찾고자하는 원소가 존재하는지 여부를 true 또는 false로 알려줍니다. O(log n)

(여기서 또한 범위는 오름 차순으로 정렬되어 있어야 합니다.)

 

#include <algorithm> 헤더를 선언함으로서 사용할 수 있고 binary_search(범위 시작, 범위 끝, 찾고자하는 값)을 넣음으로서 값이 존재한다면 true, 존재하지 않는다면 false를 반환합니다.

 

 

STL 이분 탐색 구현

 

STL binary_search 함수를 사용하여 이분 탐색을 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> arr = {1, 3, 5, 7, 9, 10, 13, 15};
    // 찾는 수가 있다면 1을 반환한다.
    cout << binary_search(arr.begin(), arr.end(), 13) << '\n'; // 1출력
    // 찾는 수가 없다면 0을 반환한다.
    cout << binary_search(arr.begin(), arr.end(), 6) << '\n'; // 0 출력
}

 

 

 

이분 탐색 관련 문제

 

 

1920번: 수 찾기

10815번: 숫자 카드