二分查找法(Golang版本)

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

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

下面首先来创建一个文件和数组

package main

import (
	"fmt"
	"math"
)

type DataStruct struct {
	Data []int
}


func main() {
	a1 := DataStruct{[]int{1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97}}

	fmt.Println(a1)
}

数组a1是一个从小到大的有序数组,总共有18个元素

 

假设说我要查找30这个值,如果按照循环的查找方法,找到30这个值要执行7次。那么如果是按照二分查找呢?好吧,二分查找的过程如下:

1. left = 1, right = 18; mid = (1+18)/2 = 9;   51 > 30    

2. left = 1, right = mid - 1 = 8; mid = (1+8)/2 = 4;   15 < 30

3. left = mid + 1 = 5, right = 8; mid = (5+8)/2  = 6;  30 = 30 查找完毕

只需要执行3次,大大减少了执行时间

下面来写一个查找的方法

func (d *DataStruct) Find(k int) int {
	left, right, mid := 1, len(d.Data), 0
	for {
        // mid向下取整
		mid = int(math.Floor(float64((left + right) / 2)))
		if d.Data[mid] > k {
            // 如果当前元素大于k,那么把right指针移到mid - 1的位置
			right = mid - 1
		} else if d.Data[mid] < k {
            // 如果当前元素小于k,那么把left指针移到mid + 1的位置
			left = mid + 1
		} else {
            // 否则就是相等了,退出循环
			break
		}
        // 判断如果left大于right,那么这个元素是不存在的。返回-1并且退出循环
		if left > right {
			mid = -1
			break
		}
	}
    // 输入元素的下标
	return mid
}

接下来试一下这个方法,把刚才main改成这样

func main() {
	a1 := DataStruct{[]int{1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97}}

	fmt.Println(a1.Find(30)) //打印 6
}

二分查找就完成了


有疑问加站长微信联系(非本文作者)

本文来自:开源中国博客

感谢作者:Zorn

查看原文:二分查找法(Golang版本)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

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