[알고리즘] 이진 탐색 알고리즘

이진 탐색이란?
이진 탐색(Binary Search)은 데이터로 정렬되어 있는 경우, 정렬된 값의 반에 해당되는 값과 계속 비교를 해서 검색 범위를 줄여, 원하는 값을 빠르게 찾아나가는 알고리즘을 말합니다.


예시
배열인 arr값이 10, 30, 50, ,80, 100, 120, 150, 180, 220, 250으로 배열에 저장되어있고,

여기서 50이 배열 어느 인덱스에 위치하는지 알고자 한다고 합시다.

배열의 최소 인덱스(nLow)는 0이고, 최대 인덱스(nHigh)는 9입니다.

최소 인덱스(nLow)와 최대 인덱스(nHigh)를 더한 후 2로 나눕니다.

그럼 중간값(nMid)이 나오게 됩니다.

입력값과 같은 값이 나올 때까지 이 과정을 반복하게 됩니다.

첫 번째에서는 

nLow = 0, nHigh = 9, nMid = (nLow + nHigh) / 2 = 4

arr[nMid]는 100이 나오게 되는데, 입력값보다 100은 큰 값이므로,

nHigh에 nMid에 1을 뺀 값을 넣습니다.(nHigh = nMid - 1)

두 번째에서는

nLow = 0, nHigh = 3, nMid = (nLow + nHigh) / 2 = 1

arr[nMid]는 30이 나오는데, 입력값보다 30은 작기 때문에

nLow에 nMid에 1 더한 값을 넣습니다.(nLow = nMid + 1)

세 번째에서는

nLow = 2, nHigh = 3, nMid = (nLow + nHigh) / 2 = 2

arr[nMid]는 50이므로, 입력값과 같은 값이 나오게 됩니다.

2번째 인덱스에 50 값을 찾았습니다.

C++ 코드로는 다음과 같습니다.

 

#include <iostream>
using namespace std;
 
void main()
{
    int arrData[10] = { 10, 30, 50, 80, 100, 120, 150, 180, 220, 250 };
 
    int nLow = 0;
    int nHigh = 9;
    int nMid = (nLow + nHigh) / 2;
    int nNum;
 
    cout << "input data : ";
    cin >> nNum;
 
    while( nLow <= nHigh )
    {
        nMid = (nLow + nHigh) / 2;
        cout << "nMid : " << nMid << endl;
        if ( arrData[nMid] == nNum )
        {
            cout << "Find Index : " << nMid << endl;
            return;
        }
        else if( arrData[nMid] < nNum )
        {
            nLow = nMid + 1;
        }
        else
        {
            nHigh = nMid - 1;
        }
    }
 
    cout << "Not Find" << endl;
}