二分検索法-POP

二分ルックアップは折半ルックアップ(Binary Search)とも呼ばれ、効率の高いルックアップ方法です.ただし、半角検索では、リニア・テーブルはシーケンス・ストレージ構造を採用する必要があり、テーブル内の要素はキーワード順に並べられています.

 public function shu()
    {
        $arr = array(1,2,4,6,7,8,9,10,13,16,17,19);
        $low = 0;
        $height = count($arr);
        $cha = 17;
        $index = $this->digui($arr, $low, $height, $cha);
        return $index;
    }
    public function digui($arr, $low, $height, $cha)
    {
        if ($arr[$height - 1] < $cha) return -1; //             
        if ($arr[$low] > $cha) return -1; //             
        $middle = intval(floor(($low + $height) / 2));
        if ($arr[$middle] == $cha) return $middle; //          ;
        if ($arr[$middle] > $cha) {    //        ，             
            return $this->digui($arr, $low, $middle, $cha);
        }
        if ($arr[$middle] < $cha) { //        ，             
            return $this->digui($arr, $middle, $height, $cha);
        }
    }