up&down이란?

어딘가에 써져있는 숫자를 맞추는 게임으로 1 ~ 50 까지 존재하는 수에서 정답을 맞추면 승리하는 게임이다. 정답이 플레이어가 외친 수보다 크면 ‘업’, 작으면 ‘다운’을 말하는 게임으로 일정 횟수(보통 5회)를 정해놓고 그 횟수를 넘어가면 사회자의 승, 작다면 플레이어의 승이 된다.

up&down에서 수를 5개로 정하는 이유!

중간값만을 부르는 전략, 예를 들어 수가 1이라고 할 때, 25 → 12 → 6 → 3 → 1 또는 26 → 13 → 7 → 4 → 2 → 1 같은 방식을 통해 최악도 6이 나오고 평균적으로 log_2(50)이 나와 대략 5.6번이 나오기 때문이다. 만약 사회자의 무조건적인 패배가 필요하다면 6번으로 정하면 사회자의 패배는 정해져있다!

이진 탐색(Binary Search) 알고리즘이란!

위에서 말한 up&down의 중간값을 부르는 전략을 사용한 알고리즘으로 정렬된 리스트에서 같은 크기의 중위값을 기준으로 두 덩어리로 나누고 필요한 부분만 탐색해 원하는 숫자를 찾는 알고리즘이다. 원하는 숫자와 리스트의 중위값이 같다면 멈추고, 크다면 리스트의 오른쪽을 검사, 작다면 리스트의 왼쪽을 검사한다.

예시

num_list = [1, 2, 3, 4 ... 99, 100]

start = 0
end = 99
find_num = 21
num_list[(start + end) / 2] = 50
find_num < 50

//find_num이 50보다 작으므로, 왼쪽만 검사해준다
end = 48
num_list[(start + end) / 2] = 25
find_num < 25

//find_num이 25보다 작으므로, 왼쪽만 검사해준다
end = 23
num_list[(start + end) / 2] = 12
find_num > 12

//find_num이 12보다 크므로, 오른쪽만 검사해준다
start = 12
num_list[(start + end) / 2] = 18
find_num > 18

//find_num이 18보다 크므로, 오른쪽만 검사해준다
start = 18
num_list[(start + end) / 2] = 21
find_num == 21

//정답! 따라서 find_num의 인덱스는 (start + end) / 2 = 20!

C를 이용하여 구현

//재귀를 이용
int	binary_search(int *arr, int find_value, int start, int end)
{
	int	mid;

	if (start > end)
		return (-1);
	mid = (start + end) / 2;
	if (find_value == arr[mid])
		return (mid);
	else if (find_value > arr[mid])
		return (binary_search(arr, find_value, mid + 1, end));
	return (binary_search(arr, find_value, start, mid - 1));
}

//비재귀적
int	binary_search(int *arr, int find_value, int len)
{
	int	start;
	int	end;
	int	mid;

	start = 0;
	end = len - 1;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (find_value == arr[mid])
			return (mid);
		else if (find_value > arr[mid])
			start = mid + 1;
		else
			end = mid - 1;
	}
	return (-1);
}

lower_bound, upper_bound, bisect_left, bisect_right

위의 코드는 만약 찾는 value값이 존재하지 않다면 (-1)을 리턴했지만 만약 이 소제목에서 언급한 함수들을 구현하고 싶다면, 리턴값으로 start, end를 잘 조작하여 반환하면 가능하다!

int	lower_bound(int *arr, int find_value, int len)
{
	int start;
	int end;
	int mid;

	start = 0;
	end = len - 1;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (find_value >= arr[mid])
			start = mid + 1;
		else
			end = mid - 1;
	}
	return (start - 1);
}