美文网首页
利用Golang实现一个类型通用的二分查找

利用Golang实现一个类型通用的二分查找

作者: MrCloudPeak | 来源:发表于2019-07-30 02:35 被阅读0次

本文讨论的重点不是二分查找,而是如何类型通用
众所周知,Golang不支持泛型,也不支持运算符重载。这给实现一个类型通用算法带来了一定困扰,好在还可以通过接口来实现
如下代码中,只要实现了SortedList接口,便可使用BinarySearch函数进行二分查找。
Golang虽然不支持泛型,但是使用接口也是可以达到类似的效果的,比如Golang自带的sort包,适合于各种类型,就是利用的这种接口机制

package main

import (
   "fmt"
)
/**
用于实现二分查找的有序列表,需要实现这个接口
其中要查找的元素,也需要放在这个list最后,因为如果这个元素不在list里,将无法与list中的元素进行比较(接口类型无法比较)
*/
type SortedList interface {
   //返回list的长度(除去需要查找的元素)
   Len() int
   //将list[i]与需要查找的元素比较,小于返回-1,等于返回0,大于返回1
   Cmp(i int) int8
}

type Person struct {
   age int
}

type SortedPersonList []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 SortedPersonList) Cmp(i int) int8 {
   //将s[i]与需要查找的元素(即s最后一个元素)比较
   return s[i].Cmp(s[len(s)-1])
}
func (s SortedPersonList) Len() int {
   //-1是为了把最后一个需要查找的元素去掉
   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
}
//这里做了一层封装,将待搜索的list,与搜索的目标作为2个参数传入
func searchPerson(list []Person, target Person) int {
   a := append(SortedPersonList(list), target)
   return BinarySearch(a)
}

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

相关文章

  • 利用Golang实现一个类型通用的二分查找

    本文讨论的重点不是二分查找,而是如何类型通用众所周知,Golang不支持泛型,也不支持运算符重载。这给实现一个类型...

  • golang循环递增数组查找值

    循环递增数组查找值 golang 1.实现要求 在循环递增数组中查找某个值 2.实现方法 使用二分法实现查找 使用...

  • 二分查找模式

    二分查找通用的模板int mid = (left + right) / 2容易溢出 二分查找的通用模板 使用“左边...

  • golang实现二分查找

    一组数据要进行二分查找,那么这个要查找的元素是有序,并且是连续存放(数组)。这样才可以进行二分查找。

  • 简单算法

    冒泡排序: while 实现的二分查找: 递归实现二分查找:

  • 算法之二分查找

    二分查找 二分查找是著名、高效并有应用广泛的查找算法。 二分常规实现 1.循环实现 下面我用python语言实现循...

  • 分治算法(swift二分法排序递归实现)

    二分查找 1、二分查找(Binary Search) 2、二分查找的基本思想 swift算法实现

  • 二分查找

    二分查找 什么是二分查找 实现原理 什么是二分查找 二分查找是从一个有序数组中找到目标元素(通常是找下标)的过程 ...

  • 二分查找

    网上找到的图片便于理解 二分查找递归实现与循环实现代码: /** 二分查找 1.二分查找又称折半查找,它是一种效率...

  • 二分查找

    数据顺序存储,有序序列 O(logn) 递归实现二分查找: 非递归实现二分查找:

网友评论

      本文标题:利用Golang实现一个类型通用的二分查找

      本文链接:https://www.haomeiwen.com/subject/iipwrctx.html