<?php

//二分查找算法

//前提：索引数组、数组已排好顺序

$a=array(1,3,4,6,8,9,11,13,15,24,25,27,30,38);

$search = 30;//要查找的数据

$len = count($a);//个数

 $r=binary_search($a,$search,0,$len-1);

 echo $r;

/*

function binary_search;

从数组$arr中的位置$begin开始到$end范围查找$s

 */

function binary_search($arr,$s,$begin,$end){

    $mid = floor(($begin+$end)/2);//定义中间的位置

    $mid_value = $arr[$mid];

    if($mid_value==$s){

        return true;

    }

    else if($mid_value > $s){

        if($begin > $mid-1){

            return false;

        }

        //中间项比$s大，去mid左边找

        $re = binary_search($arr,$s,$begin,$mid-1);

    }

    else{

        if($mid+1 > $end){

            return false;

        }

        //中间项比要找的$s小，去右边找

        $re = binary_search($arr,$s,$mid+1,$end);

        return $re;

    }

}