二分查找法(Golang版本)

原创
2017/05/08 10:10
阅读数 108

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

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

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
}

二分查找就完成了

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部