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

문제 풀이하면서 이분탐색 알고리즘이 자주 사용되는 경우가 있어서 정리해놓으려고 한다.

 

이분 탐색이란?

이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

배열 내부의 데이터가 정렬되어 있어야하만 할 수 있는 알고리즘이다.

변수 3개(low, high, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

 

이분탁샌의 구현?

탐색의 대상이 되는 자료들이 정렬되어 있어야한다.

low와 high값에 의거해 중간값 mid 값은 (low + high) / 2 이다.

arr[mid]값과 구하고자 하는 key값을 비교한다. 

: key > mid : 구하고자 하는 값이 중간값보다 높다면 low를 mid +1로 만들어 준다.

: key < mid : 구하고자 하는 값이 중간값보다 낮다면 high를 mid -1로 만들어 준다.

: key == mid : 구하고자 하는 값을 찾았으므로 중간값을 리턴한다.

low > high가 될 때까지 1~3번을 반벅호면서 구하고자 하는 값을 찾는다.

 

순환을 이용하는 방법과 반복을 이용하는 방법이 있다.

 

순환 호출을 이용한 이분 탐색 구현

int binarySearch(int key, int low, int high) {
	int mid;
    
    if(low <= high) {
    	mid = (low + high) / 2;
        
        if(key == arr[mid]) {
        	return mid;
           	}
        else if(key < arr[mid) {
        	return binarySearch(key, low, mid - 1);
            }
     	else {
        	return binarySearch(key, mid + 1, high);
            }
     	}
        return -1; //탐색 실패
}

 

반복을 이용한 이분 탐색 구현

int binarySearch(int key, int low, int high) {
	int mid;
    
    while(low <= high) {
    	mid = (low + high) / 2;
        
        if(key == arr[mid] {
        	return mid;
        }
        else if(key < arr[mid]) {
        	high = mid -1;
        }
        else {
        	low = mid + 1;
       	}
 	}
    return -1; //탐색 실패
}

 

이분 탐색의 성능은?

이분 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄인다.

이러한 탐색 범위가 더 이상 줄일 수 없는 1이 될 때의 탐색 횟수를 k라고 한다면

k = log 2 n임이 된다. 따라서 이진 탐색의 시간 복잡도는 O(log n)이 된다.