思路码荔,對半分割數(shù)組,判斷查找值會落在哪個區(qū)間具篇,不斷縮小查找區(qū)間直至找到查找的元素,或數(shù)組中只有一個元素凌埂。
$a = [1,2,3,4,5,8,9,11,12];
$x = 5;
//循環(huán)實現(xiàn)驱显,時間復雜度O(logN)
function find($need, $arr) {
var_dump($arr);
$count = count($arr);
if ($count == 1) {
if ($arr[0] == $need) return true;
return false;
}
$tmp = intval($count/2) - 1;
if ($arr[$tmp] == $need) return true;
if ($arr[$tmp] > $need) {
return find($need, array_slice($arr, 0, $tmp+1));
} else {
return find($need, array_slice($arr, $tmp + 1));
}
}
var_dump(find($x, $a));
//遞歸實現(xiàn)
function find($need, $arr) {
$count = count($arr);
if ($count == 1) {
if ($arr[0] == $need) return true;
return false;
}
$tmp = intval($count/2) - 1;
if ($arr[$tmp] == $need) return true;
if ($arr[$tmp] > $need) {
return find($need, array_slice($arr, 0, $tmp+1));
} else {
return find($need, array_slice($arr, $tmp + 1));
}
}