2017-10-26

Golang二分查找算法的简单实现

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