递归版二分查找： 核心算法:binarysearch.php //echo内容均为debug
<?php //递归 function Rank($key,&$array,$lo,$hi,$deep) { if ($lo > $hi) { echo "$key 未找到<br/>"; return -1; } //php是弱类型 利用floor向下取整(数组中会自动取整可不需要) $mid = floor($lo + ($hi - $lo) / 2); echo "deep: ".$deep." lo: ".$lo." hi:".$hi.'<br/>'; if ($array[$mid] > $key) { ++$deep; return Rank($key,$array,$lo,$mid - 1,$deep); } else if ($array[$mid] < $key) { ++$deep; return Rank($key,$array,$mid + 1,$hi,$deep); } else { echo "$key 已找到<br/>"; return $mid; } } function BinarySearch($key,&$array) { $deep = 0; sort($array); return Rank($key,$array,0,count($array) - 1,$deep); } ?>测试代码+界面：totest.php
<?php include("binarysearch.php"); echo '<html> <body> <form ENCTYPE = "multipart/form-data" action = "totest.php" method ="post" align = "center"> 查找:<input type = "text" name = "key"><br> 文件名:<input type = "file" name = "marco" value = ""><br> <input type = "submit" value = "开始"> </form> </body> </html>'; function test($key,$file,$tmp) { $ex = explode(".",$file); $suffix = array_pop($ex); if($suffix != "txt") exit(0); $data = file_get_contents($tmp); $lines = explode("\r\n",$data); $array = array(); foreach ($lines as $words) { $line = explode(' ',$words); foreach ($line as $word) $array[] = $word; } BinarySearch($key,$array); } test($_POST['key'],$_FILES['marco']['name'],$_FILES['marco']['tmp_name']); ?>运行: 非递归版: 核心算法:bianrysearch.php
<?php function BinarySearch($key,&$array) { sort($array); $lo = 0; $hi = count($array) - 1; while ($lo <= $hi) { $mid = floor($lo + ($hi - $lo) / 2); if ($array[$mid] > $key) $hi = $mid - 1; else if ($array[$mid] < $key) $lo = $mid + 1; else { //debuging echo "$key 已找到<br/>"; return $mid; } } echo "$key 未找到<br/>"; return -1; } ?>totest.php与上面相同: 实现:
