文档章节

二分查找法(Golang版本)

Zorn
 Zorn
发布于 2017/05/08 10:10
字数 448
阅读 21
收藏 0

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

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

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
粉丝 0
博文 4
码字总数 1386
作品 0
深圳
程序员
私信 提问
【数据结构与算法JavaScript实现与应用】查找算法 —— 顺序查找 PK 二分法+排序

前言 在列表中查找数据有两种方式:顺序查找和二分查找。对于一个已排序的列表,二分法无疑效率更高,因为每次可排除一半的元素,但若是对于一个无序的列表,如果先对其排序,再用二分法查找...

haoshuai1950
07/20
0
0
《算法图解》笔记(1) 二分查找

二分查找 二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回 null 。 一般而言,对于包含n个元素的列表,用二分查找最多需要l...

WMXNLFD
03/05
0
0
前端面试 - 算法篇(二分法)

前段时间换了份工作,也经历了很多面试,最终通常都会扑在算法上 虽说前端是所有程序员中,对于算法的要求最低的一个岗位,但算法依旧是进阶的必修课 于是决定记录一下与算法相关的面试题,以...

WiseWrong
2018/08/15
0
0
每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述,就是任何实现某种功能的代码片...

爱吃西瓜的番茄酱
2018/01/07
0
0
算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重要的基础问题 查找问题的基础:二分查找法 Binary Search 对于有序...

天涯明月笙
2017/09/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

skywalking(容器部署)

skywalking(容器部署) 标签(空格分隔): APM [toc] 1. Elasticsearch SkywalkingElasticsearch 5.X(部分功能报错、拓扑图不显示) Skywalking需要Elasticsearch 6.X docker network create......

JUKE
2分钟前
0
0
解决Unable to find a single main class from the following candidates [xxx,xxx]

一、问题描述 1.1 开发环境配置 pom.xml <plugin><groupId>org.springframework.boot</groupId><artifactId>spring-boot-maven-plugin</artifactId><!--一定要对上springboot版本号,因......

TeddyIH
2分钟前
0
0
Dubbo服务限制大数据传输抛Data length too large: 13055248, max payload: 8388608解决方案

当dubbo服务提供者向消费层传输大数据容量数据时,会受到Dubbo的限制,报类似如下异常: 2019-08-23 11:04:31.711 [ DubboServerHandler-XX.XX.XX.XXX:20880-thread-87] - [ ERROR ] [com.al...

huangkejie
5分钟前
0
0
HashMap和ConcurrentHashMap的区别

为了线程安全,ConcurrentHashMap 引入了一个 “分段锁” 的概念。具体可以理解把一个大的 map 拆分成 N 个小的 Map 。最后再根据 key.hashcode( )来决定放到哪一个 hashmap 中去。 hashmap ...

Garphy
6分钟前
0
0
购买SSL证书需要注意哪些问题

为了保障网站的基本安全,为网站部署SSL证书,已经是一种常态了。各大浏览器对于安装了SSL证书的网站会更友好,并且不会发出“不安全”的提示。部署SSL证书之前首先得去给网站购买一个SSL证书...

安信证书
36分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部