이진탐색(binary search)

정렬된 배열의 탐색에서 사용한다. 

배열의 중앙아 있는 값을 조사하여 찾고자하는 값이 중앙값보다 큰지 작은지를 판단한다. 

만약 크다면 찾고자하는 값은 중앙값보다 오른쪽에 있는 것이고, 작다면 중앙값보다 왼쪽에 있는 것이다. 

예를 들어 배열{1,2,3,4,5} 가 있을 때, 찾고자하는 값이 2라면 중앙값 3보다 작으므로 왼쪽에 있다.

이렇게 탐색의 범위를 반으로 줄일수 잇고, 이러한 방법에 의해 매 단계에서 검색해야할 리스트의 크기를 반으로 줄인다. 

 

다음은 이진탐색이 성공한 경우이다. 

 

만약 다음과 같이 배열안에 찾고자하는 원소가 존재하지 않는다면 탐색은 실패한다. 

 

아래는 이진탐색을 C++로 구현한 예이다. 

#include <iostream>
using namespace std;
#define ARRAY_SIZE 10

int main(void)
{
    int array[ARRAY_SIZE] = {1,3,5,9,13,15,16,18,62,79};

    int searchValue = 3;

    int firstIndex = 0;
    int lastIndex = ARRAY_SIZE-1;
    int middleIndex = (firstIndex+lastIndex)/2;
    
    bool IsSearch = false;
    
    while(!IsSearch)
    {
        if(firstIndex > middleIndex || middleIndex > lastIndex)
        {
            cout<<"찾고자 하는 원소가 배열 안에 없습니다. "<<endl;
            break;//탐색 실패
        }
        if(searchValue < array[middleIndex])
        {
            lastIndex = middleIndex-1;
            middleIndex = (firstIndex + lastIndex)/2;
        
        }
        else if(searchValue > array[middleIndex])
        {   
            firstIndex = middleIndex+1;
            middleIndex = (firstIndex + lastIndex)/2;
        }
        else    //searchValue == arry[middleIndex]
        {
            cout<<"인덱스 "<<middleIndex<<"번에 있습니다."<<endl;
            IsSearch = true; //탐색 성공
        }
        
    }
    return 0;
}