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
복사
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);
}
C
복사
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);
}
C
복사
