[알고리즘] 이진 검색(Binary Search)에 대해서 알아보자

[알고리즘] 이진 검색(Binary Search)에 대해서 알아보자

이번글에서는 이진 검색에 대해서 간략히 살펴보도록 하겠습니다. 컴퓨터 사이언스에 대한 전공을 공부하시면 2~3학년에 자료구조와 알고리즘을 배우시게 되죠? 자료구조와 알고리즘으로 들어가면 많은 분들이 고민도 많이 하게되고, 전공에 대한 회의도 많이 느끼시게 됩니다. 

하지만 계속 생각하다 보면, 그렇게 어렵지 않습니다. 컴퓨터 사이언스는 계산에 대한 머리는 가지고 있어야 하지만 배우고자는 열정과 Try-Catch에 대한 노력 및 시간을 투자하시면 충분히 이해할 수 있을겁니다. 그럼 이진 검색에 대해서 알아볼께요. 

1) 이진 검색이란?

정수를 하나 생각할테니 맞춰봅시다. 50? 너무 작네요. 75? 너무 크네요.!!  숫자를 맞출 때까지 계속 진행해보면 결국 log2N번의 내에 맞출 수 있을 겁니다. 이런식으로 탐색을 접근하는 방식이 바로 이진 탐색입니다. 

이진 탐색 프로그램은 구현하기 어려운것으로 유명하죠. 탐색중에 가장 편한 방법이 순차탐색일겁니다. 데이터 량이 작을 때는 순차탐색으로 프로그래밍 요구사항이 간단히 해결이 되니깐요. 순차탐색은 n/2번 비교한대 비해, 이진 탐색은 log2N번을 탐색하게 됩니다. 하지만 순차탐색은 검색양이 커지면 커질 수록 처리 시간이 오래걸리는 단점을 가지고 있습니다. 

100명의 데이터를 처리하는 프로그램이 갑자기 커져서 100만명을 처리해야한다고 생각해보세요. 1000만명은? 1억명은?

이런 요구사항에 대해서 순차탐색은 결코 해답이 될 수 없을겁니다. 

간략히 이진 탐색에 대해서 알아보았습니다. 그럼 위키피디아에 정의되어 있는 이진 검색에 대한 내용을 살펴보겠습니다.

이진 검색 알고리즘(binary search algorithm)은 정렬된 리스트에서 특정한 값을 찾는 알고리즘이다. 

처음 중간의 값을 임의의 값으로 선택하여, 그 값을 찾고자 하는 값과 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 된다. 이진 검색은 분할 정복 알고리즘의 한 예이다.

<참고 : 위키피디아>

여기에서 핵심은 "정렬된 리스트, 특정한 값을 찾는 알고리즘이다" 입니다. 이진 검색은 반드시 자료가 정렬이 되어 있어야 합니다. 

2) 이진 검색 알고리즘 

이진 검색의 순서는 어떻게 될까요? 여기에서 배열은 작은수부터 큰수로 정렬되어 있다고 가정하겠습니다.

1. 배열의 중간 크기를 구하고, 중간 크기의 배열 값을 가져온다. 

2. 배열의 값과 찾는 값이 동일하다면 프로그램을 종료한다.

3-1. 중간값보다 찾는 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다.(1번으로 회귀)

3-2. 중간값보다 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색한다(1번으로 회귀)

아래의 그림을 살펴보겠습니다. 

<참고 : http://glocalit.skhu.ac.kr/~mckim1/Lecture/DS/dna/index.html>

별로 어려운건 없으시죠

중간값 찾고, 중간값이 찾는 값보다 작으면 중간값 인덱스의 왼쪽으로 가서 똑같은 방식으로 찾고, 아니면 오른쪽으로 가서 찾는 방식입니다. 

3) 이진 검색 복잡도

이진 검색의 복잡도는 O(logN)입니다

윗 부분에서 이진 검색과 순차 검색의 비교 글이 나왔었는데, 실질적으로 연산 속도를 살펴보면 다음과 같이 차이가 많이 나는것을 알 수 있습니다.  이진 검색이 순차검색보다 훨씬 효율적이라는 말이 되겠지요. 

그럼 탐색 알고리즘의 복잡도는 무엇이냐?

Worst Case를 기준으로 하여 탐색에 걸리는 시간(연산 횟수)을 말합니다. 복잡도는 Big-Oh(빅오) 표기법을 많이 사용합니다.

빅오는 다항식으로 복잡도가 표현이 될 경우 가장 높은 차수가 빅오의 차수가 되는것입니다.

즉 특정 연산의 복잡도가 아래와 같다면,

이 알고리즘의 복잡도는

로 나타낼 수 있습니다.

4) 이진 검색 코드(C++, C#)

추가적으로 코드에 대한 정보 공유드립니다. 이진 검색에 대한 C++코드는 아래와 같습니다.

template<typename T>

int binary_search(const std::vector<T>& vec, unsigned start, unsigned end, const T& key)

{

    // Termination condition: start index greater than end index

    if(start > end)

    {

        return -1;

    }

 

    // Find the middle element of the vector and use that for splitting

    // the array into two pieces.

    unsigned middle = start + ((end - start) / 2);

 

    if(vec[middle] == key)

    {

        return middle;

    }

    else if(vec[middle] > key)

    {

        return binary_search(vec, start, middle - 1, key);

    }

 

    return binary_search(vec, middle + 1, end, key);

}

이진 검색에 대한 C# 코드는 아래와 같습니다.

static int BinarySearch(int[] array, int value)

{       

    int low = 0, high = array.Length - 1, midpoint = 0;

 

    while (low <= high)

    {

        midpoint = low + (high - low)/2;      

 

        // check to see if value is equal to item in array

        if (value == array[midpoint])

        {                    

            return midpoint;

        }

        else if (value < array[midpoint])

            high = midpoint - 1;

        else

            low = midpoint + 1;

    }

 

    // item was not found

    return -1;

}

이진 검색에 대해서 알아보았습니다.

머리가 아푸시죠, 식히시면서 공부 열심히하세요.

이 글이 도움이 되셨나요?

그렇다면 아래의 그림을 클릭해주세요.