Binary Search란?

어느 범위 안에 있는, 어느 수를, 중간치로 범위를 한정하면서 탐색하는 알고리즘입니다.
이번은 그 실례를 보여 드리므로 봐 주세요

실례

1에서 8까지 정수가 있습니다.
그 중에서 이번에는 7을 탐험합니다. ($T=7$로 합니다.)1, 2, 3, 4, 5, 6, 7(T), 8단계 수 $i$(0 시작)
첫 번째 수를 S, 마지막 수를 E, 그 중간 값 (내림)을 $ g_i $
$i = 0: $
$\S = 1$
$\E = 8$
$\g_0 = floor(\frac{S+E}{2}) = 4$

즉,
$i=0$ 결과1(S), 2, 3, 4(g), 5, 6, 7(T), 8 (E)$g_i$와 T를 비교하고, 만약 일치하면 거기서 종료. 이번에는 일치하지 않으므로 계속합니다.

$i=1: $
$g_i < T라면 S = g_i$
$g_i > T라면 E = g_i$
그리고 새롭게 둡니다.
이번에는 $g_0 = 4 < T$ = 7이므로
새 $S = 4$입니다.
새로운 $g_1$
$g_1 = floor(\frac{S+E}{2}) = floor(\frac{4+8}{2}) = 6$
따라서
$i=1$ 결과4(S), 5, 6(g), 7(T), 8 (E)$g_1 = 6\neq T = 7$이므로 계속.

$i=2: $
$g_0 = 6 < T$ = 7이므로 $S = g_1 = 6$
$g_2 = floor(\frac{S+E}{2}) = 7$
$i = 2$ 결과6(S), 7(g, T), 8 (E)$g_2 = T = 7$보다 무사히 탐색 종료입니다!

요약

이번은 3회로 탐색이 끝났습니다.

나는 이것이 8 개의 정수 중에서 binary search를 사용하여 탐색 할 때의 최대 단계 수가 될 것이라고 생각합니다.
자세하게 설명하면, 검색수의 최대치는 $O(log_2N)$ 되기 때문이라고 생각하고 있습니다.
왜냐하면 한 번 탐색할 때마다 탐색 범위가 대략 절반씩 깎여 가기 때문입니다. (각 단계의 회색 부분을 참조하십시오.)

엄격한 설명은 다른 곳에 양보합니다.