使用者:Viztor/Binary search algorithm

Viztor/Binary search algorithm
二叉搜索算法的演示，目標值為7
概況
複雜度
相關變量的定義

二分搜索（也稱為折半搜索算法，對數搜索，或二進切分）是計算機科學中的一種在有序數組中搜索的搜索算法。二分搜索將目標值與數組的中間元素進行比較。 如果不相等，則去掉目標值不可能存在的一半，並在另一半上進行搜索，再次將中間元素以目標值進行比較，重複這一過程，直到找到目標值。 如果搜索結束時剩下的一半為空，則目標不在數組中。 儘管想法簡單，但實現時，則需要特別注意其退出條件和中點的計算。

在最壞情況下，二分搜索以對數時間運行，進行 $O(\log n)$次比較操作（$n$是數組中的元素數，$O$是大 o 符號，$\log$是對數）。 二分搜索需要恆定的$O(1)$空間，這意味著該算法所占的空間對於任意數目元素數組都是相同的。 二分搜索只能用於有序數組。除了小數組外，二分搜索比線性搜索更快。儘管專門用於快速搜索的資料結構可以更有效（如哈希表），但二分搜索更廣泛適用各種問題。

二進制搜索有許多不同分支。 比如：分級級聯加速多個數組中相同值的二進制搜索。 分數級聯有效地解決了計算幾何和許多其他欄位中的一些搜索問題。 指數搜索將二進制搜索擴展到無界的列表。 二元搜尋樹和 B-tree 資料結構是基於二進制搜索的。

算法

對排序數組進行二進制搜索。 二進制搜索首先將數組的中間元素與目標值進行比較。 如果目標值與中間元素相匹配，則返回其在數組中的位置。 如果目標值小於中間元素，則搜索繼續在數組的下半部分。 如果目標值大於中間元素，則搜索繼續在數組的上半部分。 通過這樣做，算法消除了目標值不能在每個迭代中隱藏的一半。

程序

Given an array $A$ of $n$ elements with values or records $A_{0},A_{1},A_{2},\ldots ,A_{n-1}$sorted such that $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$, and target value $T$, the following subroutine uses binary search to find the index of $T$ in $A$.

1. Set $L$ to $0$ and $R$ to $n-1$.
2. If $L>R$, the search terminates as unsuccessful.
3. Set $m$ (the position of the middle element) to the floor of ${\frac {L+R}{2}}$, which is the greatest integer less than or equal to ${\frac {L+R}{2}}$.
4. If $A_{m}<T$, set $L$ to $m+1$ and go to step 2.
5. If $A_{m}>T$, set $R$ to $m-1$ and go to step 2.
6. Now $A_{m}=T$, the search is done; return $m$.

This iterative procedure keeps track of the search boundaries with the two variables $L$ and $R$. The procedure may be expressed in pseudocode as follows, where the variable names and types remain the same as above, floor is the floor function, and unsuccessful refers to a specific value that conveys the failure of the search. [[Category:二]] [[Category:搜尋演算法]] [[Category:Webarchive模板wayback链接]] [[Category:CS1匈牙利文来源 (hu)]] [[Category:Pages with unreviewed translations]]