查找算法：二分查找（折半查找）

1. 简介

将一个有序数组一分为二，将查找的数据与切分点比较，在哪一块区间。在将所在区间一分为二，将查找的数据与切分点比较，在哪一块区间…
三种情况：

1. 查找数据与切分点相等直接返回索引
2. 查找数据大于切分点，按切分点右侧继续查找
3. 查找数据小于切分点，按切分点左侧继续查找

1.1. 条件

1. 必须是有序数组

1.2. 效率

O(lgn)

2. 图示

3. 演示

3.1. Go版本

3.1.1. 文件树形图

binarysearch
├── binary_search.go
├── binary_search_test.go
└── go.mod

3.1.2. 代码

binary_search.go

package binarysearch

func GetIndexByData(arr []int, findData int) int {
	low := 0
	high := len(arr) - 1

	for low <= high {
		mid := (low + high) / 2
		if arr[mid] > findData {
			high = mid - 1
		} else if arr[mid] < findData {
			low = mid + 1
		} else {
			return mid
		}
	}

	return -1
}

binary_search_test.go

package binarysearch

import "testing"

func TestGetIndexByData(t *testing.T) {
	arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
	index := GetIndexByData(arr, 6)
	t.Log(index)
}

3.1.3. 测试结果

=== RUN   TestGetIndexByData
    binary_search_test.go:8: 5
--- PASS: TestGetIndexByData (0.00s)
PASS

4. 参考

• 《C/C++函数与算法速查手册》