美文网首页
二分搜索算法 Go

二分搜索算法 Go

作者: AusenZ | 来源:发表于2018-08-06 17:58 被阅读0次

说明

二分查找的数组必须是有序的,二分查找的优点是查找操作仅需要O(lgN)时间。

逻辑

首先传入的数组必须是有序的,然后算法开始时取整个数组,并通过对比将数组规模不停减半,直到发现符合寻找条件的元素为止(或者未能找到元素)。

代码

package arithmetic

import (
    "math"
)

//SearchBinary 二分查找
func SearchBinary(element interface{}, slice []interface{},
    funcCondition func(interface{}, interface{}) int) (int, bool) {

    var l, r = 0, len(slice) - 1
    var i = int((l + r + 1) / 2)
    for l != r {
        switch funcCondition(slice[i], element) {
        case -1: //slice[i] < element
            l = i + 1
            i = int((l + r + 1) / 2)
            continue
        case 0: //slice[i] == element
            return i, true
        case 1: //slice[i] > element
            r = i - 1
            i = int((l + r + 1) / 2)
            continue
        }
    }
    return len(slice), false
}

//InterfaceSearch 搜索接口
type InterfaceSearch interface {
    Len() int
    Condition(i int, element interface{}) int
    GetElement(i int) interface{}
}

//SearchBinaryOop 二分查找  面向对象
func SearchBinaryOop(element interface{}, slice InterfaceSearch) (int, bool) {

    var l, r = 0, slice.Len() - 1
    var i = int((l + r + 1) / 2)
    for l != r {
        switch slice.Condition(i, element) {
        case -1: //slice[i] < element
            l = i + 1
            i = int((l + r + 1) / 2)
            continue
        case 0: //slice[i] == element
            return i, true
        case 1: //slice[i] > element
            r = i - 1
            i = int((l + r + 1) / 2)
            continue
        }
    }
    return slice.Len(), false
}

代码说明

面向算法:通过闭包传入的判断条件判断两个元素是否相等,若相等返回元素所在数组下标,以及true 。若不相等,则通过对比元素大小,对剩余数组元素取中间下标继续循环对比。若最终未搜索到数据则返回数组长度,以及false。

面向对象:结构体通过实现接口,取代原本闭包传入的方式。

两种方式各有优缺点。主要在调用时,面向算法因为Go语言的特性问题,需要将结构数组转换成通用的[]interface{},此部分比较耗时。两种代码实现方式都可用于自身结构数组。其他编程语言情况有所不同。具体调用方式见下文。

测试代码

package  main

import (
    "AZframework/arithmetic"
    "fmt"
)

//IntSlice []int
type IntSlice []int

func (s IntSlice) Len() int           { return len(s) }
func (s IntSlice) Condition(i int, element interface{}) int {

    if s[i] == element.(int) {
        return 0
    }

    if s[i] < element.(int) {
        return -1
    }

    return 1
}

func (s IntSlice) GetElement(i int) interface{} { return s[i] }

func main() {

    var intB = 2
    var sliceC = IntSlice{1, 2, 3, 4, 5, 6}

    var interSlice = make([]interface{}, len(sliceC))

    for i, d := range sliceC {
        interSlice[i] = d
    }

    var x3, y3 = arithmetic.SearchBinary(intB, interSlice, func(a interface{}, b interface{}) int {
        if a.(int) == b.(int) {
            return 0
        }

        if a.(int) < b.(int) {
            return -1
        }

        return 1
    })
    fmt.Printf("SearchBinary %t %d\n", y3, x3)

    var x4, y4 = arithmetic.SearchBinaryOop(intB, sliceC)
    fmt.Printf("SearchBinaryOop %t %d\n", y4, x4)

}

日志输出

SearchBinary true 1
SearchBinaryOop true 1

相关文章

  • 算法-二分搜索算法

    算法:二分搜索算法(折半查找算法)时间复杂度: 二分搜索算法概述 二分搜索算法伪代码 二分搜索算法实现 二分搜索算...

  • 二分搜索算法 Go

    说明 二分查找的数组必须是有序的,二分查找的优点是查找操作仅需要O(lgN)时间。 逻辑 首先传入的数组必须是有序...

  • day17_选择排序_数组的搜索算法

    选择排序 规律: 数组的搜索算法之二分搜索法

  • 【数据结构与算法 - Swift实现】11 - 二分查找 (Bi

    二分查找是高效搜索算法中的一员,时间复杂度为O(log n)。使用搜索算法前,需要满足两个条件: 集合中的元素必须...

  • 二分搜索算法

    介绍 二分搜索是一种在有序数组中查找某一特定元素的搜索算法。这种搜索算法每一次比较都使搜索范围缩小一半。 复杂度 ...

  • 线性搜索算法 Go

    说明 线性搜索是指从数组0下标开始,依次序搜索对比的搜索方式。 代码 代码说明 面向算法:线性遍历数组,通过闭包传...

  • 二叉树的插入和搜索--python实现

    本文首先介绍了二分查找法,采用“循环”和“递归”2种方法实现。采用递归算法实现了二叉树的插入和搜索算法。 一、二分...

  • 刷前端面经笔记(九)

    1.JavaScript实现二分法查找? 二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。查找...

  • Binary Search 二分搜索

    经典的二分搜索算法 例题 74. Search a 2D Matrix 把matrix当作一个array来处理 2...

  • 算法汇总

    关于算法: 基础技巧:分治、二分、贪心排序算法:快速排序、归并排序、计数排序搜索算法:回溯、递归、深度优先遍历,广...

网友评论

      本文标题:二分搜索算法 Go

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