Golang二分查找(适用任意类型,只需实现接口)

MrCloudPeak · · 287 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
package main

import (
    "fmt"
)

type SortedList interface {
    Len() int
    Cmp(i int) int8
}

type Person struct {
    age int
}

type SortedIntList []Person

func (p Person) Cmp(cmp Person) int8 {
    if p.age == cmp.age {
        return 0
    } else if p.age > cmp.age {
        return 1
    } else {
        return -1
    }
}

func (s SortedIntList) Cmp(i int) int8 {
    return s[i].Cmp(s[len(s)-1])
}
func (s SortedIntList) Len() int {
    return len(s) - 1
}
func BinarySearch(list SortedList) int {
    lower, higher := 0, list.Len()-1
    for lower <= higher {
        //防止超过int范围
        mid := lower + (higher-lower)/2
        cmp := list.Cmp(mid)
        switch cmp {
        case 0:
            return mid
        case 1:
            higher = mid - 1
        case -1:
            lower = mid + 1
        }
    }
    return -1
}
func searchInt(list []Person, target Person) int {
    a := append(SortedIntList(list), target)
    return BinarySearch(a)
}

func main() {
    a := searchInt([]Person{{12}, {13}, {14}}, Person{14})
    fmt.Println(a)
}

本文来自:简书

感谢作者:MrCloudPeak

查看原文:Golang二分查找(适用任意类型,只需实现接口)

入群交流(和以上内容无关):加入Go大咖交流群,免费领全套学习资料或添加微信:muxilin131420 备注:入群;或加QQ群:729884609

287 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传