/ Go 语言实现二分查找算法 /
二分查找是一种高效的搜索算法,它可以在有序数据中快速查找目标值。本文将详细介绍如何使用 Go 语言实现二分查找,代码示例附带详细注释说明。
主要内容包括:
- 算法介绍
- 最简实现
- 递归实现
- 迭代实现
- 查找第一个值
- 查找最后一个值
- 处理重复值
- 边界条件
- 泛型实现
- 测试用例
希望通过具体的代码实例,可以帮助大家更好地理解二分查找原理,并练习 Go 语言算法编码能力。实现一个经典算法也有利于提高编程思维能力。
1
1. 算法介绍
二分查找针对有序数据设计,可以快速定位目标值。基本思路是:
- 从中间元素开始查找
- 如果中间元素正好是目标值,返回索引
- 如果目标值大于或者小于中间元素,在一半区间重复查找
复杂度为 O(logN)。
2
2. 最简实现
首先,一个最简单的实现是:
func binarySearch(nums []int, target int) int { low, high := 0, len(nums)-1 for low <= high { mid := low + (high-low)/2 if nums[mid] == target { return mid } else if nums[mid] < target { low = mid + 1 } else { high = mid - 1 } } return -1 }
这实现了二分查找的基本逻辑。
3
3. 递归实现
递归实现二分查找:
func recursiveSearch(nums []int, low, high, target) int { if low > high { // 退出条件 return -1 } mid := low + (high-low)/2 if nums[mid] == target { return mid } else if nums[mid] < target { return recursiveSearch(nums, mid+1, high, target) } else { return recursiveSearch(nums, low, mid-1, target) } }
递归实现二分查找关键是退出条件与递归调用。
4
4. 迭代实现
我们也可以用迭代实现二分查找:
func iterativeSearch(nums []int, target) int { low, high := 0, len(nums)-1 for low <= high { mid := low + (high-low)/2 if nums[mid] == target { return mid } else if nums[mid] < target { low = mid + 1 } else { high = mid - 1 } } return -1 }
迭代实现通常更高效,但是递归实现可以训练思维。
5
5. 查找第一个值
要查找第一个等于目标值的元素:
func searchFirstOf(nums []int, target int) int { low, high := 0, len(nums) - 1 for low <= high { mid := low + (high-low)/2 if nums[mid] > target { high = mid - 1 } else if nums[mid] < target { low = mid + 1 } else { if mid == 0 || nums[mid-1] != target { return mid } high = mid - 1 } } return -1 }
这样可以查找到目标值在数组中第一次出现的位置。
6
6. 查找最后一个值
查找最后一个等于目标值的元素:
func searchLastOf(nums []int, target int) int { low, high := 0, len(nums) - 1 for low <= high { mid := low + (high-low)/2 if nums[mid] > target { high = mid - 1 } else if nums[mid] < target { low = mid + 1 } else { if mid == len(nums)-1 || nums[mid+1] != target { return mid } low = mid + 1 } } return -1 }
这通过调整查找范围可以查找到目标值最后一次出现的位置。
7
7. 处理重复值
对含重复值的数组二分查找也是可以的:
func searchDup(nums []int, target int) bool { low, high := 0, len(nums) - 1 for low <= high { mid := low + (high-low)/2 if nums[mid] == target { return true } // 跳过重复值 for low < mid && nums[low] == nums[mid] { low++ } for high > mid && nums[high] == nums[mid] { high-- } if nums[mid] > target { high = mid - 1 } else { low = mid + 1 } } return false }
这里使用了一种跳过重复元素的方法。
8
8. 边界条件
需要注意二分查找的边界条件:
- 最小索引最小为 0
- 最大索引最大为 len(nums) - 1
- 循环退出条件 low > high
- 初始化 low 和 high
这样可以避免数组越界问题。
9
9. 泛型实现
可以使用泛型实现通用的二分查找:
func BinarySearch[T comparable](nums []T, target T) int { low, high := 0, len(nums) - 1 for low <= high { mid := low + (high-low)/2 switch { case nums[mid] < target: low = mid + 1 case nums[mid] > target: high = mid - 1 default: return mid } } return -1 }
这样可以支持所有可比较类型。
10
10. 测试用例
编写测试用例验证二分查找算法非常必要:
func TestBinarySearch(t *testing.T) { nums := []int{1, 2, 3, 4} if BinarySearch(nums, 2) != 1 { t.Error("2应该在索引1处:") } if BinarySearch(nums, 6) != -1 { t.Error("未找到 6 应返回 -1:") } }
一定要测试边界条件。
11
总结
至此我们使用 Go 语言实现了二分查找算法,并学习了递归和迭代两种实现方式,重点理解算法思想和编程技巧,可以继续扩展改进算法。
