二進制搜索 Javascript

讓我們找到中心數。那是 9。我們可以將 9 與我們正在尋找的數字進行比較。 9 等於我們正在尋找的數字。

這意味著我們的研究可以停止。我們設法在列表中找到了第 9 位！

如何在 JavaScript 中實現二進制搜索

可以使用迭代或遞歸方法實現二進制搜索。

迭代二分搜索

迭代二分搜索使用while循環來查找列表中的項目。此循環將一直運行，直到在列表中找到該項目或直到搜索到列表。

讓我們從編寫 function 執行我們的二分搜索：

讓我們從定義兩個變量開始：開始和結束。這些跟踪最高和最低值，我們的研究正在使用。我們使用 while 循環 ，它一直運行到起始編號大於結束編號。此循環計算列表開頭和結尾之間的中間數。

如果我們要找的數字等於中間的數字，則將中間的數字返回給我們的主程序。數字較小，種子值設置為等於中間數字加 1。這些比較是使用 if 語句進行的。

否則，最後的數字設置為中間數字減一。如果執行while循環後沒有找到我們的數字，則返回-1。我們稱之為基本條件。在我們的主程序中，我們`將檢查返回的數字是否等於-1。是，這意味著我們的數字沒有找到。

我們的函數還沒有工作。我們需要編寫一個主程序來命名它：

我們已經定義了一個要搜索的數字列表以及我們想要在列表中找到的數字。接下來，我們調用了 binarySearch 函數。這將做我們的研究。搜索將返回 -1 或我們正在尋找的元素的位置。

-1 表示找不到項目。如果未找到元素，則執行 else 語句的內容。否則，執行 if 語句的內容。

讓我們運行我們的代碼：

這說明我們的搜索成功了！

遞歸二分搜索

h3>

遞歸二分搜索被認為比迭代搜索更優雅。這是因為二進制搜索在列表上一遍又一遍地執行相同的操作。此行為可以使用遞歸算法實現。

打開一個新的 JavaScript 文件並粘貼以下代碼：

這段代碼與我們的第一次搜索進行相同的比較。檢查中間數字是否等於、大於或小於我們要查找的數字。

在我們的 函數，我們使用了if語句來檢查起始編號是否大於結束編號，如果是，則說明在我們指定的列表中沒有找到我們的item。在這種情況下，我們將 -1 返回給主程序。

如果我們要查找的號碼與中心號碼相同，則將中心號碼返回給主程序。如果我們正在尋找的數字大於或小於中心數字，我們的二分搜索功能將再次執行。這將一直持續到找到我們的元素。

要執行此功能，我們需要對我們的主程序進行修改：

我們還需要傳遞兩個參數：“start”和“end”的值‚Äã‚Äã。 “start”的值等於0。“end”的值等於列表的長度減一。

讓我們運行我們的代碼，看看會發生什麼：

我們的二分查找成功了！它使用與迭代方法相同的底層算法。不同之處在於，二分搜索是使用調用的函數執行的，直到找到該項目或直到列表中的搜索完成，以先到者為準。

結論

二分搜索使查找列表中的項目變得更加容易。每次執行搜索時，列表中剩餘的待查找項數會減少一半。這使得二分搜索比線性搜索更有效。

您現在可以開始像專家一樣在 JavaScript 中實現二分查找！