歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Golang二分查找算法的簡單實現

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

Copyright © Linux教程網 All Rights Reserved