每一次迭代都保證了答案仍在剩下的值裡面。
前一篇文章 二分搜尋法的實作基礎 提及了關於二分搜的核心概念：每一次迭代都排除了一些不可能是答案的值。我們今天來看看二分搜尋法有哪些應用吧！
勘根定理
對於一個連續函數 $f$，如果這個函數在 $[a, b]\subseteq \mathbb{R}$ 區間內有定義，而且 $f(a) < 0$、$f(b) > 0$，那麼勘根定理告訴我們說，中間必定存在一個 $x\in [a, b]$ 使得 $f(x)=0$。
上面這個定理只告訴我們存在至少一個根，但其實它的證明就是利用二分搜尋法的概念！而且是反方向的概念：
考慮無窮序列 ${a_i}$ 以及 ${b_i}$。他們的定義如下：$a_0=a$ 且 $b_0=b$。接著我們依序定義，對所有正整數 $i$，令 $m_i = (a_{i-1}+b_{i-1})/2$，若 $f(m_i) = 0$，則我們找到了 $x=m_i$。否則的話，我們根據 $f(m_i)$ 之值定義新的一組 $(a_i, b_i)$： $$ (a_i, b_i) = \begin{cases} (a_{i-1}, m_i) &\text{ if } f(m_i) > 0,\ (m_i, b_{i-1}) &\text{ if } f(m_i) < 0. \end{cases} $$
二分在哪裡呢？我們可以發現每一次迭代，區間 $[a_i, b_i]$ 長度是前一次迭代的 $[a_{i-1}, b_{i-1}]$ 的一半！由於 ${a_i}$ 是遞增有上界、${b_i}$ 遞減有下界、他們彼此之間距離又會趨近於 $0$，因此最終 $\lim_{i\to\infty} a_i = x^* = \lim_{i\to\infty} b_i$。由夾擠定理可得知 $f(x^*)=0$。
找出陣列中的極小點
給定一個陣列 $A[0..n-1]$，這個陣列的所有數字都不相同。假設這個陣列最左邊和最右邊的邊界都是無窮大，也就是 $A[-1]=A[n]=\infty$。請找出任何一個極小點的索引 $i$：滿足 $A[i-1] > A[i] < A[i+1]$。
找出任一個括弧組
給定一個僅包含小括弧 ( 或 ) 的字串 $S$，已知字串左界是個左括弧 (、右界是個右括弧 )。請設計一個演算法有效率地找出一個連續的一對括弧 () 子字串。