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
}
}
|
