forked from wangzheng0822/algo
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary.php
More file actions
102 lines (93 loc) · 1.97 KB
/
binary.php
File metadata and controls
102 lines (93 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
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
102
<?php
/**
* 二分查找 查找=find的元素
* @param array $numbers
* @param [type] $find
*
* @return void
* @date 2018/11/26
* @author yuanliandu
*/
function binarySearch(array $numbers, $find)
{
$low = 0;
$high = count($numbers) - 1;
return search($numbers, $low, $high, $find);
}
function search(array $numbers, $low, $high, $find)
{
/**
* notice1 循环退出条件
*/
if ($low > $high) {
return -1;
}
/**
* notice2 mid计算
*/
$mid = $low + (($high - $low) >> 1);
if ($numbers[$mid] > $find) {
//notice3 high值更新
return search($numbers, $low, $mid -1, $find);
} elseif ($numbers[$mid] < $find) {
//notice4 low值更新
return search($numbers, $mid + 1, $high, $find);
} else {
return $mid;
}
}
/**
* 求数字的平方根，保留6位小数
* @param [type] $number
*
* @return void
* @date 2018/11/26
* @author yuanliandu
*/
function squareRoot($number)
{
if ($number < 0) {
return -1;
} elseif ($number < 1) {
$min = $number;
$max = 1;
} else {
$min = 1;
$max = $number;
}
$mid = $min + ($max - $min) / 2;
while (getDecimalPlaces($mid) < 6) {
$square = $mid * $mid;
if ($square > $number) {
$max = $mid;
} elseif ($square == $number) {
return $mid;
} else {
$min = $mid;
}
$mid = $min + ($max - $min) / 2;
}
return $mid;
}
/**
* 计算数字小数点后有几位数字
* @param [type] $number
*
* @return void
* @date 2018/11/27
* @author yuanliandu <yuanliandu@qq.com>
*/
function getDecimalPlaces($number)
{
$temp = explode('.', $number);
if (isset($temp[1])) {
return strlen($temp[1]);
}
return 0;
}
// 测试二分查找给定值
$numbers = [0, 1, 2, 3, 3, 4, 5, 6, 7, 9];
$find = 1;
var_dump(binarySearch($numbers,$find));
//测试求平方根
var_dump(squareRoot(3));