-
Notifications
You must be signed in to change notification settings - Fork 487
Expand file tree
/
Copy pathInsertQuery.php
More file actions
62 lines (55 loc) · 1.98 KB
/
InsertQuery.php
File metadata and controls
62 lines (55 loc) · 1.98 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
<?php
/**
* 插入查询
*
* @author Pu ShaoWei <pushaowei0727@gmail.com>
* @date 2017/8/25
* @license MIT
* -------------------------------------------------------------
* 思路分析：对于数组长度比较大，关键字分布又是比较均匀的来说，插值查找的效率比折半查找的效率高
* -------------------------------------------------------------
* 它是二分查找的改进。
* 在英文词典里查找“apple”，你下意识里翻开词典是翻前面的书页还是后面的书页呢？如果再查“zoo”,你又会怎么查？
* 显然你不会从词典中间开始查起，而是有一定目的地往前或往后翻。
*
*/
// +--------------------------------------------------------------------------
// | 解题方式 | 这儿，可能有用的解决方案
// +--------------------------------------------------------------------------
/**
* insertQuery
*
* @param array $container
* @param $num
* @return bool|float|int
*/
function insertQuery(array $container, $num)
{
$count = count($container);
$lower = 0;
$high = $count - 1;
while ($lower <= $high) {
if ($container[ $lower ] == $num) {
return $lower;
}
if ($container[ $high ] == $num) {
return $high;
}
$left = intval($lower + $num - $container[ $lower ]);
$right = ($container[ $high ] - $container[ $lower ]) * ($high - $lower);
$middle = $left /$right;
if ($num < $container[ $middle ]) {
$high = $middle - 1;
} else if ($num > $container[ $middle ]) {
$lower = $middle + 1;
} else {
return $middle;
}
}
return false;
}
// +--------------------------------------------------------------------------
// | 方案测试 | php `this.php` || PHPStorm -> 右键 -> Run `this.php`
// +--------------------------------------------------------------------------
echo insertQuery([4, 5, 7, 8, 9, 10, 8], 8);
// 6