AK F.*ing leetcode 流浪计划之二分查找

欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。

文章目录

[toc]

一、简介

二分查找算法是通过试探性的方法,逐步缩小答案范围,最终找到结果(最优解或无解)的一种搜索算法。

该算法每次可以排除当前解集中一半的不可行解。该算法要求解集具有单调性,即某一个解不可行时,那么大于或小于该解的解都不可行。

该算法的高效之处就在于每次可以排除一半的不可行解(或留下一半可能存在可行解),使得搜索次数大大减少,提高算法的效率。这也让我们在设计验证函数时可以适当的放开一些复杂度量极。

主要适用于数组中特定条件数字位置的查询,以及一些优值的求解应用。

二、条件及解题步骤

条件:

  • 解集是一个数字区间[l, 4], 必须有 1)有序性,2)线性的(随着数字的增大或减小离最优解越近或越远)3)可以随机访问。
  • 对于某一个解,可以比较方便(复杂度不高)去判断该解是否可行。即可以设计出效率不低的验证方法checkFunc。

解题步骤

  • 判断是否可以用二分
  1. 确定解集范围 [l, r],并且是否满足有序且线性。
  2. 设计验证可行解函数 checkFunc。
  • 具体操作

step 1 初始化 [l, r],best

step 2 计算出中间值 mid

step 3 checkFunc(mid)

step 4 根据check 结果记录最优值best,并重新确定[l, r] (或者确定找到最优解返回结束)

step 5 如果l<=r 则跳转到step 2.

三、作用

常规数组查询

  1. 查询数组中特定的数字
  2. 查询数字存在的上下界
  3. 查询大于或小于某数字的上下界
  4. 翻转有序数组中一些问题的应用

推广到一般问题求最优解应用

  1. 求解平方根。
  2. 求解软件最近可用版本。
  3. 在一些求解最大或最小值问题中,不能通过动态规划,贪心等方法直接求出,但是可以验证某个值的可行性时,可以考虑二分。

四、代码框架

在有序数组查询中,固定值查询(是否存在),上下界查询是比较常用的操作。也被写成了模板,我在初学理解时,被三个模板的差异搞得很迷糊。其中主要的变化是1)终止条件的判断(l<r or l<=r or l+1<r)什么时候用哪个;2)mid 的确定,mid = (left+right)/2 (向下取整 or 向上取整)。理解各中原理固然重要,但如果每次做新题目时,都要去考虑这些问题,那么无疑对做题效率以及准确性方面会大打折扣。下面我先给出经典问题的标准写法以及其中原理,再抛出我总结的一般模板。

经典算法

在有序数组中查找定值

func BinarySearch(a []int, value int) int {
	low, high := 0, len(a)-1

	for low <= high {
		mid := (low + high) >> 1
		if a[mid] == value { // 找到答案直接返回
			return mid
		}
		
		if a[mid] < value { // mid 以及 < mid 都不可能是答案
			low = mid + 1
		} else { // mid 以及 > mid 都不可能是答案
			high = mid - 1
		}
	}
	return -1
}

在有序数组中查找定值最左位置

func findFirstPosition(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := (right + left) / 2
		// 小于一定不是解
		if nums[mid] < target {
			// 下一轮搜索区间是 [mid + 1, right]
			left = mid + 1
		} else if nums[mid] == target {
			// 下一轮搜索区间是 [left, mid]
			right = mid
		} else {
			// nums[mid] > target,下一轮搜索区间是 [left, mid - 1]
			right = mid - 1
		}
	}

	// 此处要特判
	if nums[left] == target {
		return left
	}
	return -1
}

在有序数组中查找定值最右位置

func findLastPosition(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right - left + 1) / 2 // 默认往高位走
		if nums[mid] > target {
			// 下一轮搜索区间是 [left, mid - 1]
			right = mid - 1
		} else if nums[mid] == target {
			// 下一轮搜索区间是 [mid, right]
			left = mid
		} else {
			// nums[mid] < target,下一轮搜索区间是 [mid + 1, right]
			left = mid + 1
		}
	}
	return left
}

从上面三个算法中看出,每个算法 的终止条件,right, left 重新取值,还有外面的特判都有所差别。相信写过二分算法的人都知道,经常产生数组越界,边界考虑不周等情况,最后针对用例编程,搞得代码面目全非。如果每来个新题目都要关注这些点,非常容易出错,编码效率也大大降低。

二分模板

从上面几个模板可以看出,我们要求的其实是一个最优解。由于解集本身具有单调性,那么全局最优解必然也是局部最优解。我们可以在第一个算法基础上,开一个变量best来保存当前的最优解,每次遇到可行解时都去更新最优解,算法终止时best必然也是全局最优解。

func BinarySearch(a []int, value int) int {
	low, high := 0, len(a)-1
  	best := -1 // 默认无解,也可以根据需要置其他特殊值
	for low <= high {
		// mid := (low + high) >> 1
	    // 有时候low, high比较大,求和会溢出
	    mid := low + (high-low)/2
	    
	    // 以下根据检查结果,更新best, left, right
	    switch checkFunc(mid) {
	      case 1:
	      	...
	      case 2:
	      	...
	      	...
	    }
	}
	return best
}

以上模板中终止条件和mid的生成是固定,我们要关心的是里面具体的逻辑。根据检查结果不同,再加上贪心原则,去更新best, low, high。

重写在有序数组中查找定值最左位置

func checkFunc(midVal, target int) int {
	if midVal == target {
		return 0
	}
	if midVal< target {
		return -1
	}

	return 1
}

func findFirstPositionV2(nums []int, target int) int {
	left, right := 0, len(nums)-1
	best := -1
	for left <= right {
		mid := (right + left) / 2
		checkRes := checkFunc(nums[mid], target)

		if checkRes == 0 { // 目前是一个可行解,保存该解为当前最优解,并把范围向右缩小查看是否还有更小
			best, right = mid, mid-1 // mid已经检测了,检查右边即可
		} else if checkRes<0 { // 当前位置比目标小,需要往右移使数字增大
			left = mid+1
		} else { // 当前位置比目标大,需要往左移使数字减小
			right = mid-1
		}
	}

	return best
}

在上面代码中,如果没有答案,那么checkFunc结果永远不为0,即best无解。

终止条件 left <= right ,以及更新left, right的方式保证每个数字都可能被检测到并且不需要考虑越界的情况。

每次找到更优答案后会贪心去查看更左边有没有答案。

最终可以得到最左边与目标相等的位置。

五、牛刀小试

练习1 x 的平方根

题目链接 力扣

题目大意

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。

题目解析

根据题意,是查找一个最大整数a使得a^2<=x。

显然范围可以设置为 [0, x],具有线性性,可以随机访问。

检测函数就是mid^2<=x。

更新best, left, right逻辑

如果 mid^2<=x 则best, left = mid, mid+1.

否则right = mid-1

注意,1)由于x = [0, intmax32]。mid := left + (right-left)/2

  1. mid*mid 有可能超出 int范围 ,可以用mid<=x/mid代替mid^2<=x, (mid >0, 0的情况一开始就判断)

AC代码

func mySqrt(x int) int {
	if x==0 {return 0}
	left , right := 1, x
	best := -1

	for left <= right {
		mid := left + (right-left)/2
		if mid <= x/mid { // 可行解,更新最优解,并查看有没有更优
			best, left = mid, mid+1
		} else {// 不可行解,查看更小解
			right = mid-1
		}
	}

	return best
}

练习2 供暖器

题目链接:力扣

题目大意

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在,给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置,请你找出并返回可以覆盖所有房屋的最小加热半径。

说明:所有供暖器都遵循你的半径标准,加热的半径也一样。

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1,那么所有房屋就都能得到供暖。
示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1,这样所有房屋就都能得到供暖。
示例 3:

输入:houses = [1,5], heaters = [2]
输出:3

提示:

1 <= houses.length, heaters.length <= 3 * 10^4
1 <= houses[i], heaters[i] <= 10^9

题目解析

可以知道加热半径范围是[0,10^9], 具有线性性,可以随机访问。

可以尝试给定一个半径,测试以这个半径是不是可以供暖全部房屋。

checkFunc 设计如下

先对房屋和暖气进行排序。

由于所有的房屋都要供应到。贪心原理,初始i, j=0,0。检查当前暖气是否可以照到当前房屋。如果不行,说明要么当前暖气太在左边了,需要看看右边的暖气可不可以照到。要么是暖气太在右边了(再往后移也不行了)。

最后 ,判断一下i==len(House)。

利用双指针法, 复杂度O(n+m)

总复杂度 O(log(10^9) * (m+n))

思路

func checkFunc(houses []int, heaters []int, radius int) bool {

}


func findRadius(houses []int, heaters []int) int {
	// 排序
	sort.Slice(houses, func(i, j int) bool {
		return houses[i]<houses[j]
	})
	sort.Slice(heaters, func(i, j int) bool {
		return heaters[i]<heaters[j]
	})
	best := int(10e9)
	left, right := 0, int(10e9)
	for left<= right {
		mid := (right+left)>>1
		if checkFunc(houses, heaters, mid) { // 可行解,贪心查看有没有更好解, 区间往小移
			best, right = mid, mid-1
		} else {
			left = mid+1
		}
	}

	return best
}

AC代码

func abs(a int) int {
	if a<0 {return -a}
	return a
}
func checkFunc(houses []int, heaters []int, radius int) bool {
	i, j:=0,0
	for ;i<len(houses) && j<len(heaters); {
		if abs(houses[i] - heaters[j])<=radius{
			i++
		}else {j++}
	}
	return i==len(houses)
}

func findRadius(houses []int, heaters []int) int {
	// 排序
	sort.Slice(houses, func(i, j int) bool {
		return houses[i]<houses[j]
	})
	sort.Slice(heaters, func(i, j int) bool {
		return heaters[i]<heaters[j]
	})
	best := int(10e9)
	left, right := 0, int(10e9)
	for left<= right {
		mid := (right+left)>>1
		if checkFunc(houses, heaters, mid) { // 可行解,贪心查看有没有更好解, 区间往小移
			best, right = mid, mid-1
		} else {
			left = mid+1
		}
	}

	return best
}

/*
[1,2,3]
[2]
[2]
[2]
[1,2,3,4]
[1,4]
[1,5]
[2]
[4,3,2,1]
[1,4]
*/

六、代码模板

func BinarySearch(a []int, value int) int {
	low, high := 0, len(a)-1
  best := -1 // 默认无解,也可以根据需要置其他特殊值
	for low <= high {
		// mid := (low + high) >> 1
    // 有时候low, high比较大,求和会溢出
    mid := low + (high-low)/2
    
    // 以下根据检查结果,更新best, left, right
    switch checkFunc(mid) {
      case 1:
      	...
      case 2:
      	...
      	...
    }
	}
	return best
}

此模板适用于只需要一个验证可行解的函数,有些情况下判断可行解可能有多层嵌套判断,需要适当改造,不过此模板已经适用于大多数情况。

七、总结

主要内容:

  1. 二分查找算法是通过试探性的方法,逐步缩小答案范围,最终找到结果(最优解或无解)的一种搜索算法。
  2. 适用条件
    • 解集是一个数字区间[l, 4], 必须有 1)有序性,2)线性的(随着数字的增大或减小离最优解越近或越远)3)可以随机访问。
    • 对于某一个解,设计出验证函数checkFunc去验证可行性。
  3. 解题的基本框架比较固定,关键在于checkFunc的设计,以及解区间的确定。

笔者水平有限,有写得不对或者解释不清楚的地方还望大家指出,我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目(首先AK F.*ing leetcode),有些leetcode题目不是很容易看出来二分思路,可略过。给大家准备了一些题目,供大家练习参考。干他F.*ing (Fighting?)。

八、实战训练

代码基础训练题

光说不练假把式,学完了怎么也要实操一下吧,快快动用把刚才那2题A了。

  1. x 的平方根 题目链接 力扣

  2. 供暖器 题目链接 力扣

AK leetcode

leetcode相关题目都在下面了,拿起武器挨个点名呗。

力扣 二分查找题目列表


以上题目太多,大家适当选择就行,下面还有进阶题目。

大神进阶

也可以去vjudge Problems - Virtual Judge 搜索相关题号

poj

http://poj.org/problem?id=3349

以下将序号替换就是题目链接。

  1. 3349
  2. 3274
  3. 1840
  4. 2002
  5. 2503
  6. 3122
  7. 1064
  8. 3579
  9. 2503
  10. 3977

hdu

http://acm.hdu.edu.cn/showproblem.php?pid=1597

以下将序号替换就是题目链接。

  1. 1597 find the nth digit
  2. 2578
  3. 2141
  4. 3763
  5. 2199
  6. 2899
  7. 1969
  8. 4768

本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。

在这里插入图片描述

二分加贪心 求最长递增子序列

1赞