PHP自定义函数完成二分查找实例(binary_search)

原创 阁主  2020-06-22 18:05:18  阅读 3219 次 评论 0 条
摘要:

最近在学习算法,本篇作自己学习二分查询的笔记,同时也分享给正在学习的朋友!

必要条件

想要完成二分查找这个算法,最要保证的两个前提就是:

(1)确保存有数据的数组为索引数组

(2)在第一个条件下,数组中的数据还需要是已经排序好的(小到大,大到小)

算法原理

二分查找示例动图

原理:数组在排序后,每次都找该数组的某一段的中间项,并跟要找的目标进行“对比”

(1)如果刚好相等,则就算找出来了

(2)如果中间项比目标大,就只要去左边的那一半中找

(3)如果中间项比目标小,就只要去右边的那一半中找

演示实例代码

下面代码为演示数组的二分查找算法(递归方法):

<?php
$arr1 = [2, 5, 8, 10, 15, 18, 22, 24, 24, 28, 33, 35, 50, 55, 56, 57, 60, 61, 62, 66, 70];
$search = 18; //具体分析,可以将该数据修改为不同的值,比如2,5,8
//假设有一个函数,它能够从某一个数组$arr中的某个下标范围($start---$end)中找到指定的数据$value
//这里,假设:$start一定不能大于$end,否则,我们就认为找不到了!
function binary_seach($arr, $value, $start, $end)
{
    if ($start > $end) {
        return false;
    }
    #往下取整(去小数)
    $mid = floor(($start + $end) / 2);  //取得两个下标中的中间下标(一半)
    $mid_value = $arr[$mid];  //中间项的值
    #如果中间值是刚好找的值,就算找出来了
    if ($mid_value == $value) {
        return true;
    }
    #如果中间项比目标大,直就要去左边的那一半找
    elseif ($mid_value > $value) {
        $new_start = $start;
        $new_end = $mid - 1;
        return binary_seach($arr, $value, $new_start, $new_end);
    }
    # 如果中间项比目标小,就只要去右边的那一半中找
    else {
        $new_start = $mid + 1;
        $new_end = $end;
        return binary_seach($arr, $value, $new_start, $new_end);
    }
}
$len = count($arr1); //数组长度
$result = binary_seach($arr1, $search, 0, $len - 1);
var_dump($result);

代码嵌笔记实例

下面代码为演示数组的二分查找算法(带笔记版本):

<?php
//演示数组的二分查找算法:
//前提:
// 1,索引数组;
// 2,数组是已经排好序的了。

$arr1 = [2, 5, 8, 10, 15, 18, 22, 24, 24, 28, 33, 35, 50, 55, 56, 57, 60, 61, 62, 66, 70];
$search = 18; //具体分析,可以将该数据修改为不同的值,比如2,5,8
//原理:每次都找该数组的某一段的中间项,并跟要找的目标进行“对比”
//1,如果刚好相等,则就算找出来了
//2, 如果中间项比目标大,就只要去左边的那一半中找
//3, 如果中间项比目标小,就只要去右边的那一半中找

//假设有一个函数,它能够从某一个数组$arr中的某个下标范围($start---$end)中找到指定的数据$value
//这里,假设:$start一定不能大于$end,否则,我们就认为找不到了!
function binary_seach($arr, $value, $start, $end)
{
    if ($start > $end) {
        return false;
    }
    #往下取整(去小数)
    $mid = floor(($start + $end) / 2);  //取得两个下标中的中间下标(一半)
    $mid_value = $arr[$mid];  //中间项的值
    #如果中间值是刚好找的值,就算找出来了
    if ($mid_value == $value) {
        return true;
    }
    #如果中间项比目标大,直就要去左边的那一半找
    elseif ($mid_value > $value) {
        $new_start = $start;
        $new_end = $mid - 1;
        return binary_seach($arr, $value, $new_start, $new_end);
    }
    # 如果中间项比目标小,就只要去右边的那一半中找
    else {
        $new_start = $mid + 1;
        $new_end = $end;
        return binary_seach($arr, $value, $new_start, $new_end);
    }
}
$len = count($arr1); //数组长度
$result = binary_seach($arr1, $search, 0, $len - 1);
var_dump($result);

for语句版本

下面代码为for循环完成二分方法,原理都差不多:

<?php
$arr1 = [2, 5, 8, 10, 15, 18, 22, 24, 24, 28, 33, 35, 50, 55, 56, 57, 60, 61, 62, 66, 70];
$search = 28; //具体分析,可以将该数据修改为不同的值,比如2,5,8
$result = bin_search($arr1, $search, 0, count($arr1) - 1);
var_dump($result);

function bin_search($arr, $value, $start, $end)
{
    for ($i = 1; $i > 0; $i++) {
        if ($start > $end) {
            #最终只会剩下一个数值,如果依然不匹配,$start永远为1,$end永远为0
            #如果在数组中没找到搜索的值,$start会大于$end,结束循环
            return false;
        }
        #计算$start和$end的中间位置(floor函数去小数取整)
        $mid = floor(($start + $end) / 2);
        $mid_value = $arr[$mid];
        #如果运气好刚刚好找到的中间值就是要找的值
        if ($mid_value == $value) {
            return true;
        }
        #中间值大于要找的目标值,则只要去中间值的左边找.
        if ($mid_value > $value) {
            $start = $start;
            $end = $mid - 1;
        } #中间值小于于要找的目标值,则只要去中间值的右边找.
        elseif ($mid_value < $value) {
            $start = $mid + 1;
            $end = $end;
        }
    }
}
本文地址:https://www.mainblog.cn/238.html
版权声明:本文为原创文章,版权归 阁主 所有,欢迎分享本文,转载请保留出处!
免责申明:有些内容源于网络,没能联系到作者。如侵犯到你的权益请告知,我们会尽快删除相关内容。

评论已关闭!