Golang二分查找算法的簡單實現
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
}
}
