이진 탐색

이진 탐색(binary search): 정렬된 배열에서 탐색 범위를 절반으로 줄여 가며 목표 값을 탐색

 

정렬된 배열 arr에 대하여 탐색할 범위의 양 끝 인덱스를 각각 low와 high라 하고, 이 둘의 중앙값인 \(mid=(low+high)/2\)를 설정하여 찾고자 하는 값 value와 mid를 비교한다. value=mid이면 목표 값을 발견했으므로 탐색을 종료하고, value<mid라면 high를 mid로 갱신해 mid의 왼쪽 sub-array에 대해 다시 탐색을, value>mid라면 low를 mid로 갱신해 mid의 오른쪽 sub-array에 대해 탐색을 진행한다.

 

이진 탐색 알고리즘

N개의 입력에 대하여 탐색 범위가 N → N/2 → N/4 → N/8 ... 1으로 줄어드므로 \(O(logN)\)의 시간복잡도를 가진다.

 

이진 탐색 구현 - 순환

int binary_search_recur(int key, int lot, 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_recur(key, low, mid-1);	//왼쪽 부분리스트 탐색
        }
        else {
        	return binary_search_recur(key, mid+1, high);	//오른쪽 부분리스트 탐색
        }
    }
    return -1;	//탐색 실패
}

 

이진 탐색 구현 - 반복

int binary_search_iter(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;	//탐색 실패
    }
}

시간복잡도 자체는 순환 호출로 구현한 것과 동일하나(O(logN)) 함수 호출을 이용한 context switching, push/pop 과정이 없으므로 순환 호출보다 빠르다.