|
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
|
package
main
import
(
"fmt"
)
type Searchable
interface
{
Len()
int
Less(
int
,
int
) bool
Equal(
int
,
interface
{}) bool
}
type List []
int
func (l List) Len()
int
{
return
len(l)
}
func (l List) Less(first
int
, second
int
) bool {
if
l[first] < l[second] {
return
true
}
return
false
}
func (l List) Equal(index
int
, item
interface
{}) bool {
if
value, ok := item.(
int
); ok {
if
l[index] == value {
return
true
}
}
return
false
}
func main() {
list := []
int
{
1
,
2
,
3
,
5
,
9
}
index := binSearch(list,
3
)
fmt.Printf(
"The index of 3 in the list is %d\n"
, index)
index = binSearch(list,
4
)
fmt.Printf(
"The index of 4 in the list is %d\n"
, index)
}
func binSearch(list List, item
interface
{})
int
{
startFlag :=
0
stopFlag := list.Len() -
1
middleFlag := (startFlag + stopFlag) /
2
for
(!list.Equal(middleFlag, item)) && (startFlag < stopFlag) {
if
list.Less(startFlag, stopFlag) {
startFlag = middleFlag +
1
}
else
{
stopFlag = middleFlag -
1
}
middleFlag = (startFlag + stopFlag) /
2
}
if
list.Equal(middleFlag, item) {
return
middleFlag
}
else
{
return
-
1
}
}
|
本文转自 ponpon_ 51CTO博客，原文链接：http://blog.51cto.com/liuxp0827/1355505，如需转载请自行联系原作者
