介绍
二分查找(Binary Search)是一种高效的查找算法,用于在有序数组中查找特定元素的位置。二分查找的前提是数组必须是有序的,否则无法保证正确性。
算法步骤如下:
- 初始化左右指针,左指针为数组的起始位置,右指针为数组的结束位置。
- 当左指针小于等于右指针时,执行以下步骤:
- 计算中间元素的索引,可以使用 (左指针 + 右指针) / 2 或者 左指针 + (右指针 - 左指针) / 2 来避免整数溢出问题。
- 如果中间元素等于目标元素,返回中间元素的索引。
- 如果中间元素大于目标元素,说明目标元素可能在左侧,将右指针更新为中间元素的前一个位置。
- 如果中间元素小于目标元素,说明目标元素可能在右侧,将左指针更新为中间元素的后一个位置。
- 如果循环结束时仍未找到目标元素,表示目标元素不存在于数组中,返回一个表示未找到的特定值(如 -1)。
代码示例
package main
import "fmt"
// 迭代
func binarySearch1(arr *[]int, target int, left, right int) int {
for left < right {
//在arr[left...right]中查找target
//mid := (left + right) / 2
//注意:这里容易产生bug(r+l溢出int最大值),改写成如下方式
mid := left + (right-left)/2
if (*arr)[mid] == target {
return mid
} else if (*arr)[mid] > target {
//在arr[left...middleIndex - 1]中查找target
right = mid - 1
} else {
//在arr[middleIndex + 1...right]中查找target
left = mid + 1
}
}
fmt.Println("没找到")
return -1
}
// 递归
func binarySearch2(arr *[]int, target int, left, right int) int {
if left > right {
fmt.Println("没找到")
return -1
}
//mid := (left + right) / 2
mid := left + (right-left)/2
if (*arr)[mid] == target {
return mid
} else if (*arr)[mid] > target {
return binarySearch2(arr, target, left, mid-1)
} else {
return binarySearch2(arr, target, mid+1, right)
}
}
func main() {
arr := []int{1, 3, 5, 7, 9}
target1 := binarySearch1(&arr, 5, 0, len(arr)-1)
target2 := binarySearch2(&arr, 5, 0, len(arr)-1)
fmt.Println("找到了!下标为:", target1)
fmt.Println("找到了!下标为:", target2)
}
复杂度
时间复杂度:
- 最坏情况下,目标元素不在数组中,二分查找需要执行的操作次数是 log₂(n)(以 2 为底的对数),其中 n 是数组的长度。每次迭代或递归都将搜索范围缩小为原来的一半,直到搜索范围为空。因此,时间复杂度为 O(log n)。
- 最好情况下,如果目标元素恰好是数组的中间元素,那么时间复杂度为 O(1),即常数时间。这是因为只需一次比较就能找到目标元素。
每次迭代或递归都将搜索范围缩小一半,所以时间复杂度都是O(logN),递归法的性能比迭代法的略差。
空间复杂度:
- 二分查找的空间复杂度为 O(1),即常数空间。算法只需要使用几个变量来存储左右指针和中间索引,不随数组规模的增长而增加额外的空间占用。