算法篇——二分查找

2021年12月29日 · 164 字 · 1 分钟

本系列文章将学习/复习常用算法和数据结构。希望能够深入浅出的将复杂的知识讲清楚、说明白。

本文介绍第一个基础算法：二分查找。二分查找算法可以在有序的数组中快速查询指定值。

  • 要求：有序数组
  • 时间复杂度：O(logN)
  • 空间复杂度：O(1)

例子

大家应该玩过数字猜大小的游戏，接下来看看实际过程。

主持人从1~10选择1个数字，参与者每次猜1个数字，主持人给出提示正确/大了/小了。次数最少的获胜。

线性查找

  • 主持人选定数字5。
  • 参与者：10
  • 主持人：大了
  • 参与者：9
  • 主持人：大了
  • 参与者：8
  • 主持人：大了
  • …
  • 参与者：5
  • 主持人：正确

参与者采用线性报数方式，从最大的数字开始报，每次减1直到猜中。上面的例子主持人选的数字是5，参与者猜了6次（10,9,8,7,6,5)。效率是O(N)。

主持人的大了/小了提示没有利用上，这肯定不是效率最高的方法。

二分查找

  • 主持人选定数字8。
  • 参与者：5
  • 主持人：小了
  • 参与者：7
  • 主持人：小了
  • 参与者：8
  • 主持人：正确

参与者根据主持人的大了/小了提示每次调整猜测范围直到猜中。上面的例子中主持人选的数字是8，参与者猜了3次：

  1. (0+10)/2 => 5，小了，所以下一次应该猜 比5大的数字，从 5 ~ 10继续猜
  2. (5+10)/2 => 7(8也可以)，小了，所以下一次继续猜比7大的数字，从7~10继续猜
  3. (7+10)/2 => 8(9也可以)，正确

可以看到二分查找法每次都能过滤掉1半的数据，达到了O(logN)的时间复杂度

代码示例

给定一个有序数组，返回指定值的索引，如果有序数组不存在该值，返回-1。

思路：

  1. 找中间值，(0 + 数组最后一位的所以)/2得到中间值的位置，然后对比中间值和目标值大小
  2. 如果目标值比中间值小，那么目标值在数组前半部分，应该继续查找 0 ~ 数组中间索引-1的这部分
  3. 如果目标值比中间值大，那么目标值在数组后半部分，应该继续查找 数组中间索引+1 ~ 数组结尾的这部分

为什么继续查找时中间索引要+1或者-1移动？

因为中间值已经比对过了，不满足条件，所以可以直接跳过中间值往前面后者后面一个位置继续查找

package main

import "fmt"

func main() {
	fmt.Println(search([]int{1, 2, 3, 4, 5, 6, 7}, 5))
}

func search(nums []int, target int) int {
	begin := 0
	end := len(nums) - 1
	for begin <= end { // 开始位置不能超过结束位置，超过证明所以数据都查过了
		midIndex := (begin + end) / 2 // 中间索引
		midValue := nums[midIndex]    // 中间值
		fmt.Printf("check pos(%v) value(%v)\n", midIndex, midValue)
		if target < midValue { // 目标值比中间值小，所以在左边，将end移动到中间索引-1
			end = midIndex - 1
			continue
		}
		if target > midValue { // 右半边，begin移动到中间索引+1
			begin = midIndex + 1
			continue
		}
		// 相等
		return midIndex
	}
	return -1
}

输出如下

check pos(3) value(4)
check pos(5) value(6)
check pos(4) value(5)
4
qrcode