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
103
104
105
106
107
108
109
110
111
112
113
114
115
| <?php
namespace Patterns\Algorithm;
class BinarySearch
{
/**
* 查找元素是否在数组中，返回其位置
* @param $key
* @param array $data
* @param $dataSize
* @return float|int
*/
public function search($key, array $data, $dataSize)
{
$low = 0;
$high = $dataSize - 1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($key < $data[$mid]){
$high = $mid - 1;
} else if ($data[$mid] < $key){
$low = $mid + 1;
} else {
return $mid;
}
}
return -1;
}
/**
* 查找第一次出现
* @param int $key
* @param array $data
* @param int $dataSize
* @return int
*/
public function findFirst(int $key, array $data, int $dataSize):int
{
$low = 0;
$high = $dataSize - 1;
$out = -1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($data[$mid] === $key){
$out = $mid;
$high = $mid - 1;
} else if($data[$mid] > $key){
$high = $mid - 1;
} else {
$low = $mid + 1;
}
}
return $out;
}
/**
* 查找最后一次出现
* @param int $key
* @param array $data
* @param int $dataSize
* @return int
*/
public function findLast(int $key, array $data, int $dataSize):int
{
$low = 0;
$high = $dataSize - 1;
$out = -1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($key < $data[$mid]){
$high = $mid - 1;
} else if($key === $data[$mid]){
$low = $mid + 1;
$out = $mid;
} else {
$low = $mid + 1;
}
}
return $out;
}
}
include_once "./Sort.php";
$array = [3, 5, 7, 7, 7, 7, 7, 7, 10, 10, 10, 15, 17, 18, 18, 35, 78, 78];
$sort = new Sort();
$array = $sort->quick($array);
$sortSearch = new BinarySearch();
$needle = 1;
echo 'exists: ' . $sortSearch->search($needle, $array, count($array)), PHP_EOL;
echo 'First: ' . $sortSearch->findFirst($needle, $array, count($array)), PHP_EOL;
echo 'Last: ' . $sortSearch->findLast($needle, $array, count($array)), PHP_EOL;
|
