常见算法基础题思路简析(四)-二分搜索篇
标签: algorithms
[TOC]
本文对和 二分搜素 有关的常见算法基础题思路分类进行分析和总结,并以 Java 为例,适当指出需要注意的编程细节
- 相关题目和代码在 GitHub: https://github.com/brianway/algorithms-learning
- 题目见
com.brianway.learning.algorithms.lectures.binarysearch
包
求完全二叉树的节点个数
题目见 CountNodes
思路:
- 计算根节点到最左节点的高度 h
- 同理,计算根节点到其右孩子的最左节点的高度 hr
- 如果 h > hr,则节点个数为:根节点右子树的节点数+1(根节点)+根节点左子树的节点数
- 如果 h <= hr,则节点个数为 根节点左子树的节点数+1(根节点)+根节点右子树的节点数
注意:
- 计算 hr 时,
current = root.right
, 初始值为 1(代表根节点) - h > hr,说明右子树为满二叉树,高度为 h-2,
根节点右子树的节点数+1
可直接计算,为2^(h-2)
- 同理,h <= hr,说明左子树为满二叉树,高度为 h-1
最左原位
题目见 Find
思路:类似二分搜索,当 a[i]=i
时终止,有序数组且元素各不相等,所有 a[i] 每次的增量是要大于下标 i 每次的增量 1 的。
- 判断边界条件
- lo = 0, hi = n-1,开始二分搜索
- 若
a[i] > i
,则 任意 j > i,有a[j] > j
,所以只可能出现在左半部分,故 hi = mid - 1 - 若
a[i] < i
,则 任意 j < i,有a[j] < j
,所以只可能出现在右半部分,故 lo = mid + 1
注意:
- 边界条件:
arr[0] > n - 1 || arr[n - 1] < 0
时无解,直接返回 - 最后求得
arr[mid] = mid
->res = arr[mid]
后,记得赋值hi = mid - 1
,且不能跳出循环,因为要找 最左原位,所以需要继续循环下去。
元素最左出现
题目见 LeftMostAppearance
思路:这里就是一个简单的二分查找,唯一不同的是,当 arr[mid] = num
时,不是在 res = mid
后直接退出循环,而是需要赋值 hi = mid - 1
继续循环
局部最小值位置
题目见 LocalMin
思路:
- 判断两端边界情况,满足条件(
arr[0]<arr[1]
或者arr[n-2]>arr[n-1]
)则直接返回结果 - 判断
arr[mid]
和arr[mid - 1]
的大小,若arr[mid]
大,则一定有个局部最小出现在左边 - 否则,判断
arr[mid]
和arr[mid + 1]
的大小,若arr[mid]
大,则一定有个局部最小出现在右边 - 若都不满足,则局部最小为
arr[mid]
注意:
- 注意数组为空,长度为 1,以及其他边界情况
- 思路中 2,3 步的依据就是,先有 1 中段边界判断,所以一定有两端元素大于其紧邻元素(
arr[0]>arr[1]
且arr[n-1]>arr[n-2]
)。数组要么一直递减到边界的紧邻元素从而结束循环,要么在这个过程中遇到某个局部最小,所以一定是有解的。
循环有序数组最小值
题目见 MinValue
思路:循环有序数组截出一个连续的子数组还是循环有序的。在每次循环中进行一下判断:
- 若
arr[lo] < arr[hi]
,说明子数组已经升序,直接返回arr[lo]
。 否则,说明数组不升序,进行下面的步骤 - 若
arr[lo] > arr[mid]
,最小值出现在左半部分 - 若
arr[lo] < arr[mid]
,最小值出现在右半部分(因为说明arr[lo] ~ arr[mid]
是升序的) - 若
arr[lo] = arr[mid]
,最小值为第一个小于arr[lo]
或者就是arr[lo]
本身
注意:
- 注意可能有重复元素的问题,所以在遇到
arr[lo] = arr[mid]
时,需要遍历lo ~ hi
之间的元素来找到最小值 - 这里的左右指针更新需要注意,
hi = mid
和lo = mid
,而不是mid-1
和mid+1
,因为不能漏掉元素
快速N次方
题目见 QuickPower
思路:求出 k 的 1,2,4,8....次方作为中间值 tmp,减少相乘的次数
- 每次把 N 右移一位,若该位为 1,则将结果乘以中间值 tmp
- 每次令中间值 tmp 等于自己的平方(对应于第一步中的位移操作)
注意:
- 注意越界问题,按题目要求,求 mod 某个数后的结果