[Algorithm] 이진 탐색

개요

공부를 진행하다 오랜만에 이진 탐색을 꺼내려니 기억이 잘 나지 않아서 정리를 해두었다. 단순한 알고리즘이라, 정리해두고 기억이 나지 않을때 가끔씩 살펴보려 한다. 

이진 탐색 알고리즘(Binary Search Algorithm)

정렬과 함께 가장 기초인 알고리즘으로 꼽힌다. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 

정확히 설명하면 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단해 맨 앞부터 검색하거나 중간부터 검색한다.

 

이진 탐색의 원리는 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 반복하는 것으로 생각하면 된다. 단, 이진 탐색을 위해서는 자료가 순서에 따라 정렬되어 있어야 한다. 

이진 탐색의 예시 : 77을 찾아라

위의 예시를 살펴보자. 우선 50부터 탐색을 진행한다. 77은 50보다 크므로, 왼쪽 포인터를 오른쪽으로 이동한다. 그다음 절반인 75를 비교한다. 77은 75보다 크므로 왼쪽을 오른쪽으로 이동하면 된다. 다음은 87이며, 87은 77보다 작으므로 오른쪽 포인터를 왼쪽으로 이동한다. 이렇게 범위를 좁혀나가면 7번 이내에 무조건 숫자를 맞추게 된다. 

 

이를 c언어 코드로 확인해보자

int binarySearch(T arr[], T val, int first, int last) {
    if (first > last) return -1;
    int mid = (first + last) / 2;
    if (val == arr[mid]) return mid;
    else if (val < arr[mid]) return binarySearch(arr, val, first, mid-1);
    else return binarySearch(arr, val, mid + 1, last);

주어진 리스트 가운데 지점의 값을 비교해보고 그게 찾는 값보다 크면 뒤쪽 반을 잘라버리고, 작으면 앞쪽 반을 자른 다음 그 자른 리스트를 대상으로 똑같이 진행하면 된다. 즉, 재귀함수를 통해서 반복을 이어 나가다보면 숫자를 찾는 것이다. 

 

이진 탐색은 순차 탐색에 비해 굉장히 빠르지만, 사전을 든 예시에서 볼 수 있듯이 미리 정렬이 되어있어야 한다. 경우에 따라서는 쓰기 곤란한 경우도 있다는 점이 단점이다. 

---

참고문헌

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

이진 탐색 - 나무위키