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

相关阅读：