Go 实现二分查找算法
二分查找算法简介：二分查找算法对有序数组有效，二分搜索是查找数组中的目标值。
在一个有序数组中，将数组分成两段，将要查询的铁元素和分割点比较：
- 如果相等，直接返回，说明数据找到
- 目标元素大于分割点，在分割点右边继续查找
- 元素小于分割点，在分割点左侧继续查找
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g6GXGMKI-1654416113888)(https://zh.wikipedia.org/wiki/File:Binary_search_into_array.png)]
二分查找算法模板：
代码语言：javascript复制int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = (right left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
再有个标准写法
代码语言：javascript复制int BinarySearch(int array[], int n, int value)
{
int left = 0;
int right = n - 1;
//如果这里是int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：
//1、下面循环的条件则是while(left < right)
//2、循环内当 array[middle] > value 的时候，right = mid
while (left <= right) //循环条件，适时而变
{
int middle = left ((right - left) >> 1); //防止溢出，移位也更高效。同时，每次循环都需要更新。
if (array[middle] > value)
{
right = middle - 1; //right赋值，适时而变
}
else if(array[middle] < value)
{
left = middle 1;
}
else
return middle;
//可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多
//如果每次循环都判断一下是否相等，将耗费时间
}
return -1;
}
Go-二分查找算法
给定一个有序数组，查找第一个等于 target 的下标，找不到返回 -1.
代码中有一个要注意的是溢出问题： mid := low ((high - low) >> 1) // 溢出
代码实现如下:
代码语言：javascript复制package algorithm
import (
"fmt"
"testing"
)
func binarySearch(arr []int, target int) int {
low := 0
high := len(arr) - 1
for low <= high {
//mid := (low high) / 2
mid := low ((high - low) >> 1)
//fmt.Println(mid)
if arr[mid] > target {
high = mid - 1
} else if arr[mid] < target {
low = mid 1
} else {
return mid
}
}
return -1
}
func TestBinarySearch(t *testing.T) {
/*arr := make([]int, 1024*1024, 1024*1024)
for i := 0; i < 1024*1024; i {
arr[i] = i 1
}*/
//arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
//QuickSort(arr, 0, len(arr)-1)
//fmt.Println(arr)
arr := []int{1, 2, 5, 8, 9, 10, 12, 30, 45, 63, 234}
id := binarySearch(arr, 9)
if id != -1 {
fmt.Println(id, arr[id])
} else {
fmt.Println("没有找到数据")
}
}
执行结果如下：
代码语言：javascript复制=== RUN TestBinarySearch
3 8
--- PASS: TestBinarySearch (0.00s)
PASS
