[알고리즘] 이진탐색 (binary search)

이진 탐색은 중앙 값을 찾고 찾고자 하는 항목이 왼쪽에 있는지 오른쪽에 있는지 알아내어 탐색 범위를 반씩 줄여나간다.

비교가 이루어 질 때마다 탐색 범위가 급격하게 졸어들기 때문에 정렬된 배열을 탐색할 때는 이진탐색이 빠르다.

데이터의 삽입이나 삭제가 빈번할 경우에는 적합하지 않다.

 

의사코드

binary_search(list, low, high):

	middle <- low에서 high사이의 중간 위치
    if(탐색값 == list[middle])
    	return middle;
	else if(탐색값 < list[middle])
    	return list[0]부터 list[middle-1]에서의 탐색;
    else if(탐색값 > list[middle])
    	return list[middle+1]부터 list[high]에서의 탐색;

 

구현 방법에는 순환 호출과 반복 두가지가 있다.

 

순환 호출

int binary_search(int key, int low, int high)
{
	int mid;
    
    if(low <= high) {
    	mid = (low + high) / 2;
        if(key == list[mid]) //탐색성공
        	return mid;
        else if(key < list[mid]) //왼쪽 부분 리스트 탐색
        	return binary_search(key, low, mid - 1);
        else //오른쪽 부분 리스트 탐색
        	return binary_search(key, mid + 1, high);
    }
    return -1; //탐색 실패
}

 

반복

int binary_search(int key, int low, int high)
{
	int mid;
    
    while(low <= high) {
    	mid - (low + high) / 2;
        if(key == list[mid])
        	return mid;
        else if(key > list[mid]) //오른쪽부분탐색
        	low = mid + 1; 
        else //왼쪽부분탐색
        	high = mid - 1;
    }
  	return -1;
}