[알고리즘/C++] - 이분 탐색(이진 탐색, Binary Search)

이분 탐색에 적절한 짤을 찾지 못해 슬픈 가나디..

안녕하세요?

안녕하세요?

안녕하세요?

안녕하세요?

안녕하세요?

안녕합니다.

오늘 알아볼 알고리즘은 이분탐색입니다.

 

이분 탐색(이진 탐색, Binary Search)

: 오름차순으로 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고, 두 리스트 중 목표에 해당하는 숫자가 존재하는 리스트를 선택하는 과정을 반복하며 점점 탐색의 범위를 줄여나가는 방법

 

발그림

 

발그림이지만 (진짜발그림주의) 이해를 높이기 위해 제가 직접 그림을 그려왔습니다. 

탐색 절차

1. 오름차순으로 정렬된 리스트 하나를 준비합니다.

2. 우리가 찾고자하는 값을 a, 리스트의 중간값을 b라고 가정하고 목표값과 리스트의 중간값을 비교합니다. 

2-1. 만약 중간값 b가 a보다 크다면 중간값의 왼쪽에 해당하는 구간만을 검사하면 되고, 그 반대의 경우엔 오른쪽 구간을 검사합니다. 이렇게 중간값을 검사하는 것만으로 탐색의 범위가 절반이 줄어들게 됩니다!.

3. 과정을 계속 반복하며 중간값과 목표값 a가 같게 되는 경우, 탐색을 종료합니다. 

3-1. 만약 찾는 값이 존재하지 않는다면, 탐색 범위가 없어질 때까지 탐색을 반복하다가 종료하게 됩니다.

 

이분 탐색의 시간복잡도

이분 탐색은 기본적인 탐색에 비해 정말 빠른 탐색 속도를 자랑하기 때문에 많은 곳에서 활용되고 있습니다. 

예를 들며 1000개의 데이터 중 하나의 값을 찾고자 한다면 단순한 탐색으로는 최소 1번에서 최대 1000회까지의 탐색이 필요합니다.

하지만 이분 탐색을 활용한다면, 2^10=1024->따라서 최대 10번의 탐색만으로도 데이터를 찾을 수 있습니다!

이처럼 이분탐색은 탐색하고자 하는 데이터의 길이가 2배로 늘어나더라도 위처럼 한번의 검사만으로 탐색이 가능하므로,

O(log₂n)의 시간복잡도를 가집니다.

이분 탐색의 사용 조건

이분 탐색의 사용 조건이라고 대문짝만하게 써놓았지만 사실 조건은 하나 뿐입니다.

탐색하려는 자료가 반드시 순서에 따라 정렬된 상태여야 한다

만약 순서대로 정렬되어 있지 않다면 중간값을 비교하여 해당하지 않는 범위에 목표값이 반드시 없다고 보장할 수 없기 때문입니다..

이분 탐색 구현 예시

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == target)
            return mid; 
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return -1; 
}

 

코드를 보면 처음, 끝, 중간값 총 3가지의 값이 추가로 필요한 것을 알 수 있습니다. 

처음과 끝 인덱스는 우리가 탐색하고자 하는 범위를 알고자 함입니다. 이 둘을 더하고 2로 나눈 값을 통해 중간값의 위치를 계산하기도 합니다.

중간값은 당연히 목표값과의 비교를 위해 존재합니다.  

bool binary_search(begin, end, value);

놀랍게도 C++의 라이브러리 <algorithm>은 이를 따로 구현할 필요없이 함수를 통해 제공해주기도 합니다. 이 함수의 경우, 시작과 끝범위, 찾고자 하는 값을 넣어주면 해당 값이 범위 안에 존재하는지의 여부를 bool값으로 알려줍니다. 존재여부만 빠르게 알아내야하는 경우라면 이 함수를 사용하는 것도 나쁘지 않은 선택인 것 같네용

---

이분 탐색의 경우, 이전에 배웠던 정렬과 함께 기초적이고 필수적인 알고리즘 요소입니다. 어렵지 않은 개념이니 천천히 살펴보고 공부해보면 좋을 것 같습니다.

https://solved.ac/problems/tags/binary_search

solved.ac

백준은 또 친절히 이분 탐색에 대한 문제들을 1000여개 정도 마련해두었네요

심심할 때 몇분제 풀어보셔용