Can you summarize the following document?
        
  二分搜尋只對有序陣列有效。二分搜尋先比較陣列中位元素和目標值。如果目標值與中位元素相等,則返回其在陣列中的位置;如果目標值小於中位元素,則搜尋繼續在前半部分的陣列中進行。如果目標值大於中位元素,則搜尋繼續在陣列上部分進行。由此,演算法每次排除掉至少一半的待查陣列。

  給予一個包含formula_5個帶值元素的陣列formula_6或是記錄formula_7,使formula_8,以及目標值formula_9,還有下列用來搜尋formula_9在formula_6中位置的子程式。  這個迭代步驟會持續透過兩個變數追蹤搜尋的邊界。有些實際應用會在演算法的最後放入相等比較,讓比較迴圈更快,但平均而言會多一層迭代。

  以上程式只適用於"完全"匹配,也就是尋找一個目標值的位置。不過,因為有序陣列的順序性,將二分搜尋演算法擴充套件到能適用大致匹配並不是很重要。舉例來說,二分搜尋演算法可以用來計算一個賦值的排名(或稱秩,比它更小的元素的數量)、前趨(下一個最小元素)、後繼(下一個最大元素)以及最近鄰。搜尋兩個值之間的元素數目的範圍查詢 (資料結構)可以藉由兩個排名查詢(又稱秩查詢)來執行。

  除直接在一個陣列中查詢元素外,可用在插入排序中。

  

  static int binary_search(int[] arr, int start, int end, int khey)

  在1946年,約翰·莫奇利在摩爾學院講座上第一次提出二分搜尋的概念。1957年,威廉·皮特遜發表了第一個應用插值搜尋的演算法。在此時,每個發表的二分搜尋演算法只對長度為2的冪減一的陣列有用。直到1960年,德里克·亨利·萊默發表了一個對於所有長度的陣列都適用的演算法。1962年,赫爾曼·博滕布魯赫發表了一個用ALGOL 60寫的二分搜尋,將判斷相等的步驟放到演算法末尾。雖然將平均迭代次數增加一,但是每次迭代中的比較次數減少了1次。均勻二分搜尋則是史丹佛大學的A. K.錢德拉在1971年發明的。1986年,伯納德·查澤爾和列奧尼達斯·吉巴斯引入了分散層疊來解決計算幾何中大量存在的搜尋問題。

  儘管二分查詢的基本思想相對簡單,但細節可以令人難以招架... — 高德納  當喬恩·本特利將二分搜尋問題佈置給專業程式設計課的學生時,百分之90的學生在花費數小時後還是無法給出正確的解答,主要因為這些錯誤程式在面對邊界值的時候無法執行,或返回錯誤結果。1988年開展的一項研究顯示,20本教科書裡只有5本正確實現了二分搜尋。不僅如此,本特利自己1986年出版的《程式設計珠璣》一書中的二分搜尋演算法存在整數溢位的問題,二十多年來無人發現。Java語言的庫所實現的二分搜尋演算法中同樣的溢位問題存在了九年多才被修復。
在電腦科學中,二分查詢演算法(英語:binary search algorithm),也稱折半搜尋演算法(英語:half-interval search algorithm)、對數搜尋演算法(英語:logarithmic search algorithm),是一種在有序陣列中查詢某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始,如果中間元素正好是要查詢的元素,則搜尋過程結束;如果某一特定元素大於或者小於中間元素,則在陣列大於或小於中間元素的那一半中查詢,而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空,則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。