이진 탐색 알고리즘

이진 탐색

이진 탐색은 정렬된 레코드에서 원하는 값이 들어가 있는 인덱스를 찾기 위해 사용하는 알고리즘이다. 분할 정복 방식의 알고리즘으로서 최악의 경우 O(logn) 속도를 가지는 알고리즘이다.

분할 정복(Divide and Conquer)이란 알고리즘의 문제를 작은 부분으로 분할하여 해결하는 작은 부분의 문제를 해결하고 결합하여 원래의 문제 크기로 만들어 문제를 해결하는 방식이다.

동작 원리

1. 먼저 정렬된 레코드에서 중간 값을 선택한다.
2. 중간 값과 찾는 값을 비교한다.
3. 이후
   1. 중간 값 > 찾는 값이면 중간 값보다 큰 값 들이 들어가 있는 레코드에서 이진 탐색을 반복한다.
   2. 중간 값 < 찾는 값이면 중간 값보다 작은 값 들이 들어가 있는 레코드에서 이진 탐색을 반복한다.
   3. 중간 값 == 찾는 값이면 중간 값을 리턴하며 함수가 종료 된다.
4. 만약 큰 값 또는 작은 값 들이 들어가 있는 레코드가 존재 하지 않는다면 -1을 리턴하게 하며 전체 종료가 된다.

코드

c++

#include<iostream>
#include<vector>

using namespace std;

int BinarySearch(vector<int> arr, int target, int high, int low)
{
    // 중간 값을 찾는다.
    int mid = (high + low)/2;

    // 전체 종료 조건 1( 전체 레코드에서 값이 없을 때)
    if(low > high)
        return -1;

    // 전체 종료 조건 2( 값을 찾았을 때)
    if(arr[mid] == target){
        return mid;
    }

    // 중간 값이 클 때
    else if(arr[mid] > target){
        return BinarySearch(arr, target, high, mid+1);
    }

    //  중간 값이 작을 때
    else if(arr[mid] < target){
        return BinarySearch(arr, target, mid-1, low);
    }
}

실제 동작

오름차순으로 정렬된 레코드가 있다.

1, 10, 25, 40, 59, 100, 200, 312

이 배열에서 200의 값을 찾아보자.

첫번째 시도

우선 가운데에 있는 임의의 값 40을 선택한다.
선택한 값 40과 찾고자 하는 값 200과 비교한다.
선택한 값 40 보다 찾고자 하는 값이 크므로
40보다 우측에 있는 59, 100, 200, 312으로
이진 탐색을 진행한다.

두번째 시도

59, 100, 200, 312

가운데에 있는 임의의 값 100을 선택한다.
선택한 값 100은 찾고자 하는 값 200보다 작으므로
100 보다 우측에 있는 200, 312 값으로 이진 탐색을 진행한다.

세번째 시도

200, 312

두개 중에서 고를 땐 작은 값을 선택하게 되므로
200이 선택된다. 200은 찾고자 하는 값과 같으므로
200의 인덱스인 6을 반환하며 함수가 종료 된다.

최악의 상황 연산횟수

레코드 수	선형 탐색	이진 탐색
10	10	4
100	100	7
1000	1000	10
10000	10000	14

하나 하나 전부 찾아야 하는 선형 탐색이 선형적으로 횟수가 증가할 때 이진 탐색은 log의 방식으로 증가하기 때문에 횟수가 많이 증가하지 않는 것을 볼 수 있다.