forked from m9rco/algorithm-php
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinaryQuery.php
More file actions
60 lines (57 loc) · 1.97 KB
/
BinaryQuery.php
File metadata and controls
60 lines (57 loc) · 1.97 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
<?php
/**
* @example 二分查找
* @author ShaoWei Pu <[email protected]>
* @date 2017/6/17
* @license Mozilla
* -------------------------------------------------------------
* 思路分析：数组中间的值floor((low+top)/2)
* -------------------------------------------------------------
* 先取数组中间的值floor((low+top)/2)然后通过与所需查找的数字进行比较，
* 若比中间值大则将首值替换为中间位置下一个位置，继续第一步的操作；
* 若比中间值小，则将尾值替换为中间位置上一个位置，继续第一步操作
* 重复第二步操作直至找出目标数字
*/
/**
* 非递归版 二分查找
* @param array $container
* @param $search
* @return int|string
*/
function BinaryQuery( array $container,$search){
$top = count($container);
$low = 0;
while ( $low <= $top){
$mid = intval( floor( ($low + $top ) / 2) );
if( !isset($container[$mid]) ) return '没找着哦';
if( $container[$mid] == $search) return $mid;
$container[$mid] < $search && $low = $mid+1;
$container[$mid] > $search && $top = $mid-1;
}
}
// var_dump( BinaryQuery([0,1,2,3,4,5,6,7,8,9],9) );
/*
* double(8)
*/
/**
* 递归版 二分查找
* @param array $container
* @param $search
* @param int $low
* @param string $top
* @return int|string
*/
function BinaryQueryRecursive(array $container,$search,$low = 0,$top = 'default'){
$top == 'default' && $top = count($container );
if( $low <= $top ){
$mid = intval( floor( $low + $top ) /2 );
if( !isset($container[$mid]) ) return '没找着哦';
if( $container[$mid] == $search) return $mid;
if( $container[$mid] < $search ){
return BinaryQueryRecursive($container,$search,$mid+1,$top);
}else{
return BinaryQueryRecursive($container,$search,$low,$mid-1);
}
}
}
// var_dump( BinaryQueryRecursive([0,1,2,3,4,5,6,7,8,9],9) );