成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

PHP算法之二分查找

Soarkey / 2537人閱讀

摘要：二分查找的定義二分查找也稱折半查找，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。算法的要求從上面的定義我們可以知道，滿足該算法的要求必須如下兩點(diǎn)必須采用順序存儲結(jié)構(gòu)。

二分查找的定義 
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。
算法的要求

從上面的定義我們可以知道，滿足該算法的要求必須如下兩點(diǎn)：

必須采用順序存儲結(jié)構(gòu)。

必須按關(guān)鍵字大小有序排列。

算法的步驟

其實(shí)，二分查找也還是比較容易理解的，大概就是一分為二，然后兩邊比較，保留有效區(qū)間，繼續(xù)一分為二查找，直到找到或者超出區(qū)間則結(jié)束，所以二分查找的基本步驟是：

確定要查找的區(qū)間

確定要二分時(shí)的參照點(diǎn)

區(qū)間內(nèi)選取二分點(diǎn)

根據(jù)二分點(diǎn)的值，綜合左右區(qū)間情況以及求解的目的，舍去一半無用的區(qū)間

繼續(xù)在有效區(qū)間重復(fù)上面的步驟

算法源碼

這里，我主要采用遞歸和非遞歸兩種方法實(shí)現(xiàn)，具體如下：

首先第一種是非遞歸的算法實(shí)現(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;
    // 最低點(diǎn)比最高點(diǎn)大就退出
    while ($lower <= $high) {
        // 以中間點(diǎn)作為參照點(diǎn)比較
        $middle = intval(($lower + $high) / 2);
        if ($arr[$middle] > $number) {
            // 查找數(shù)比參照點(diǎn)小，舍去右邊
            $high = $middle - 1;
        } else if ($arr[$middle] < $number) {
            // 查找數(shù)比參照點(diǎn)大，舍去左邊
            $lower = $middle + 1;
        } else {
            // 查找數(shù)與參照點(diǎn)相等，則找到返回
            return $middle;
        }
    }
    // 未找到，返回-1
    return -1;
}

然后第二種是遞歸的算法實(shí)現(xiàn)，算法如下：

/**
 * @param array $arr 待查找區(qū)間
 * @param int $number 查找數(shù)
 * @param int $lower 區(qū)間最低點(diǎn)
 * @param int $high 區(qū)間最高點(diǎn)
 * @return int
 */
function binary_search_recursion(&$arr, $number, $lower, $high) {
    // 以區(qū)間的中間點(diǎn)作為參照點(diǎn)比較
    $middle = intval(($lower + $high) / 2);
    // 最低點(diǎn)比最高點(diǎn)大就退出
    if ($lower > $high) {
        return -1;
    }
    if ($number > $arr[$middle]) {
        // 查找數(shù)比參照點(diǎn)大，舍去左邊繼續(xù)查找
        return binary_search_recursion($arr, $number, $middle + 1, $high);
    } elseif ($number < $arr[$middle]) {
        // 查找數(shù)比參照點(diǎn)小，舍去右邊繼續(xù)查找
        return binary_search_recursion($arr, $number, $lower, $middle - 1);
    } else {
        return $middle;
    }
}
算法的使用

需求是在一個(gè)排列好的區(qū)間（$arr）中，查找一個(gè)數(shù)（$number）的所在位置，所以，調(diào)用算法查找如下：

// 待查找區(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í)間復(fù)雜度分析

在有序數(shù)組中如果用暴力的算法去查找，也就是逐個(gè)遍歷比較，那么時(shí)間復(fù)雜度是O(n)；但是，用二分查找后，因?yàn)槊看慰梢陨崛ヒ话氩檎覅^(qū)間，所以會將時(shí)間復(fù)雜度減少到O(logn)，算法更優(yōu)。

最后

又到了無聊的客套話時(shí)間，老規(guī)律，有問題直接留言，有想法直接說，有錯誤直接提出來，我都會及時(shí)回復(fù)的，謝謝。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/29421.html

相關(guān)文章

  • 用 PHP 的方式實(shí)現(xiàn)的各類算法合集

    摘要：數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。 項(xiàng)目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...

    Karrdy 評論0 收藏0

  • 用 PHP 的方式實(shí)現(xiàn)的各類算法合集

    摘要：數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。 項(xiàng)目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...

    pakolagij 評論0 收藏0

  • 用 PHP 的方式實(shí)現(xiàn)的各類算法合集

    摘要：數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。 項(xiàng)目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...

    leonardofed 評論0 收藏0

  • PHP面試：常見查找算法一篇說透

    摘要：我們現(xiàn)在來看二分搜索算法的兩種變形插值搜索和指數(shù)搜索。插值搜索是對二分搜索算法的改進(jìn)，插值搜索可以基于搜索的值選擇到達(dá)不同的位置。 預(yù)警 在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復(fù)雜度。因?yàn)榱η笸ㄋ滓锥?，所以篇幅可能較長，大伙可以先Mark下來，每天抽時(shí)間看一點(diǎn)理解一點(diǎn)。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。 開篇 和排序類似，搜索或者叫做...

    付永剛 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<