1

PHP之二分查找的实现

 2 years ago
source link: https://panda843.github.io/article/395626462.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

PHP之二分查找的实现

发表于 2017-12-28 | 分类于 开发 | | 浏览 次 | 字数统计: 325 | 阅读时长 ≈ 1

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

<?php
    #二分查找
    function binarySearch(Array $arr, $target) {
        $low = 0;
        $high = count($arr) - 1;

while($low <= $high) {
            $mid = floor(($low + $high) / 2);
            #找到元素
            if($arr[$mid] == $target) return $mid;
            #中元素比目标大,查找左部
            if($arr[$mid] > $target) $high = $mid - 1;
            #重元素比目标小,查找右部
            if($arr[$mid] < $target) $low = $mid + 1;
        }

#查找失败
        return false;
    }

$arr = array(1, 3, 5, 7, 9, 11);
    $inx = binarySearch($arr, 1);
    var_dump($inx);
?>
-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作！
Error: API rate limit exceeded for 141.164.63.164. (But here's the good news: Authenticated requests get a higher rate limit. Check out the documentation for more details.)

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK