資訊專欄INFORMATION COLUMN
摘要：二分查找的定義二分查找也稱折半查找，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。算法的要求從上面的定義我們可以知道，滿足該算法的要求必須如下兩點必須采用順序存儲結構。
二分查找的定義
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。算法的要求
從上面的定義我們可以知道，滿足該算法的要求必須如下兩點：
必須采用順序存儲結構。
必須按關鍵字大小有序排列。
算法的步驟其實，二分查找也還是比較容易理解的，大概就是一分為二，然后兩邊比較，保留有效區(qū)間，繼續(xù)一分為二查找，直到找到或者超出區(qū)間則結束，所以二分查找的基本步驟是：
確定要查找的區(qū)間
確定要二分時的參照點
區(qū)間內選取二分點
根據(jù)二分點的值，綜合左右區(qū)間情況以及求解的目的，舍去一半無用的區(qū)間
繼續(xù)在有效區(qū)間重復上面的步驟
算法源碼這里，我主要采用遞歸和非遞歸兩種方法實現(xiàn)，具體如下：
首先第一種是非遞歸的算法實現(xiàn)，算法如下：
/**
* 二分查找算法
* @param array $arr 待查找區(qū)間
* @param int $number 查找數(shù)
* @return int 返回找到的鍵
*/
function binary_search($arr, $number) {
// 非數(shù)組或者數(shù)組為空，直接返回-1
if (!is_array($arr) || empty($arr)) {
return -1;
}
// 初始變量值
$len = count($arr);
$lower = 0;
$high = $len - 1;
// 最低點比最高點大就退出
while ($lower <= $high) {
// 以中間點作為參照點比較
$middle = intval(($lower + $high) / 2);
if ($arr[$middle] > $number) {
// 查找數(shù)比參照點小，舍去右邊
$high = $middle - 1;
} else if ($arr[$middle] < $number) {
// 查找數(shù)比參照點大，舍去左邊
$lower = $middle + 1;
} else {
// 查找數(shù)與參照點相等，則找到返回
return $middle;
}
}
// 未找到，返回-1
return -1;
}
然后第二種是遞歸的算法實現(xiàn)，算法如下：
/**
* @param array $arr 待查找區(qū)間
* @param int $number 查找數(shù)
* @param int $lower 區(qū)間最低點
* @param int $high 區(qū)間最高點
* @return int
*/
function binary_search_recursion(&$arr, $number, $lower, $high) {
// 以區(qū)間的中間點作為參照點比較
$middle = intval(($lower + $high) / 2);
// 最低點比最高點大就退出
if ($lower > $high) {
return -1;
}
if ($number > $arr[$middle]) {
// 查找數(shù)比參照點大，舍去左邊繼續(xù)查找
return binary_search_recursion($arr, $number, $middle + 1, $high);
} elseif ($number < $arr[$middle]) {
// 查找數(shù)比參照點小，舍去右邊繼續(xù)查找
return binary_search_recursion($arr, $number, $lower, $middle - 1);
} else {
return $middle;
}
}
算法的使用
需求是在一個排列好的區(qū)間（$arr）中，查找一個數(shù)（$number）的所在位置，所以，調用算法查找如下：
// 待查找區(qū)間 $arr = [1, 3, 7, 9, 11, 57, 63, 99]; // 非遞歸查找57所在的位置 $find_key = binary_search($arr, 57); // 遞歸查找57所在的位置 $find_key_r = binary_search_recursion($arr, 57, 0, count($arr)); // 輸出打印 print_r($find_key); print_r($find_key_r);時間復雜度分析
在有序數(shù)組中如果用暴力的算法去查找，也就是逐個遍歷比較，那么時間復雜度是O(n)；但是，用二分查找后，因為每次可以舍去一半查找區(qū)間，所以會將時間復雜度減少到O(logn)，算法更優(yōu)。
最后又到了無聊的客套話時間，老規(guī)律，有問題直接留言，有想法直接說，有錯誤直接提出來，我都會及時回復的，謝謝。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://systransis.cn/yun/29421.html
摘要：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏輯結構數(shù)據(jù)元素之間的相互關系稱為邏輯結構。 項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...
摘要：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏輯結構數(shù)據(jù)元素之間的相互關系稱為邏輯結構。 項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...
摘要：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏輯結構數(shù)據(jù)元素之間的相互關系稱為邏輯結構。 項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...
摘要：我們現(xiàn)在來看二分搜索算法的兩種變形插值搜索和指數(shù)搜索。插值搜索是對二分搜索算法的改進，插值搜索可以基于搜索的值選擇到達不同的位置。 預警 在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復雜度。因為力求通俗易懂，所以篇幅可能較長，大伙可以先Mark下來，每天抽時間看一點理解一點。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。 開篇 和排序類似，搜索或者叫做...
閱讀 2116·2023-04-25 19:03
閱讀 1269·2021-10-14 09:42
閱讀 3455·2021-09-22 15:16
閱讀 1029·2021-09-10 10:51
閱讀 1659·2021-09-06 15:00
閱讀 2434·2019-08-30 15:55
閱讀 516·2019-08-29 16:22
閱讀 916·2019-08-26 13:49
