Binary Search 응용하기

https://en.wikipedia.org/wiki/Binary_search_algorithm

Binary search algorithm - Wikipedia

binary search를 책으로 배우고 실제로 응용할때 binary search 코드를 응용해야하는 경우가 있습니다

 

이번 포스팅은 어떻게 binary search를 변형할 것인가?와 관련된 내용입니다~

 

학술적 내용 및 기술은 wikipedia를 참조해주세요.

 

https://www.acmicpc.net/problem/2512

2512번: 예산

예산 문제는 Binary Search를 사용하면 풀리는 문제인데요!

 

일반적인 binary search는 찾고자 하는 값이 배열안에 있다고 생각하고 탐색을 수행합니다.

binary search(low, high, value){
	int mid = (low+high)/2;
    if(low>high)
    	return -1;
	if(Array[mid]==value){
    	return mid;
    }else if(Array[mid] < value){
    	return binary search(mid+1,high,value);
    }else{
    	return binary search(low,mid-1, vlaue);
    }
}

예를 들면 

key	1	2	3	4	5
value	90	100	110	120	130

위의 배열에서 value 100을 binary search로 찾으면 2이란 키값이 나옵니다.

 

그런데 103을 찾으려 하면?

 

100은 103보다 작고 110은 103보다 커서 low high가 반전되고 -1이 나옵니다.

 

문제를 풀려면 어떻게 접근해야 할까요?

 

이때 100을 value로 갖는 key 2는 the leftmost element가 되고, 110을 value로 갖는 key 3은 the rightmost element가 되는데요.

 

문제에 맞게 leftmost element를 찾을지 rightmost element를 찾을지 결정해서 사용하면 됩니다!

 

the leftmost element를 찾는 binary search

int bs_leftmost_element(int low, int high, int value) {
	int mid = floor((low + high) / 2);
	
	if (low >= high) {
		return low;
	}

	if (Array[mid] == value) {
		return mid;
	}
	else if (Array[mid] < value) {
		return bs_leftmost_element(mid + 1, high, value);
	}
	else {
		return bs_leftmost_element(low, mid, value);
	}
}

the rightmost element를 찾는 binary search

int bs_rightmost_element(int low, int high, int value) {
	int mid = floor((low + high) / 2);

	if (low >= high) {
		return high;
	}

	if (Array[mid] == value) {
		return mid;
	}
	else if (Array[mid] < value) {
		return bs_rightmost_element(mid, high, value);
	}
	else {
		return bs_rightmost_element(low, mid - 1, value);
	}
}

같은 binary search지만 용도에 따라 조금씩 변하는 binary search에 대해서 알아보았습니다

 

다음 포스팅에서 만나요!