二分查找法（Golang版本）

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

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

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
}

二分查找就完成了

有疑问加站长微信联系（非本文作者）