forked from m9rco/algorithm-php
-
Notifications
You must be signed in to change notification settings - Fork 103
/
Copy pathBinaryQuery.php
101 lines (94 loc) · 2.67 KB
/
BinaryQuery.php
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
<?php
/**
* 二分查找
*
* @author ShaoWei Pu <[email protected]>
* @date 2017/6/17
* @license MIT
* -------------------------------------------------------------
* 思路分析：数组中间的值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;
}
}
/**
* 递归版 二分查找
*
* @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);
}
}
}
// +--------------------------------------------------------------------------
// | 方案测试 | php `this.php` || PHPStorm -> 右键 -> Run `this.php`
// +--------------------------------------------------------------------------
var_dump(BinaryQuery([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 9));
/*
* double(8)
*/
var_dump(BinaryQueryRecursive([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 9));
/*
array(7) {
[0] =>
int(3)
[1] =>
int(4)
[2] =>
int(5)
[3] =>
int(6)
[4] =>
int(7)
[5] =>
int(8)
[6] =>
int(9)
}
*/