常见算法基础题思路简析(四)-二分搜索篇

原创
2017/09/28 22:09
阅读数 147

常见算法基础题思路简析(四)-二分搜索篇

标签: algorithms


[TOC]


本文对和 二分搜素 有关的常见算法基础题思路分类进行分析和总结,并以 Java 为例,适当指出需要注意的编程细节

求完全二叉树的节点个数

题目见 CountNodes

思路:

  1. 计算根节点到最左节点的高度 h
  2. 同理,计算根节点到其右孩子的最左节点的高度 hr
  3. 如果 h > hr,则节点个数为:根节点右子树的节点数+1(根节点)+根节点左子树的节点数
  4. 如果 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 的。

  1. 判断边界条件
  2. lo = 0, hi = n-1,开始二分搜索
  3. a[i] > i,则 任意 j > i,有 a[j] > j,所以只可能出现在左半部分,故 hi = mid - 1
  4. 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

思路:

  1. 判断两端边界情况,满足条件(arr[0]<arr[1] 或者 arr[n-2]>arr[n-1])则直接返回结果
  2. 判断 arr[mid]arr[mid - 1] 的大小,若 arr[mid] 大,则一定有个局部最小出现在左边
  3. 否则,判断 arr[mid]arr[mid + 1] 的大小,若 arr[mid] 大,则一定有个局部最小出现在右边
  4. 若都不满足,则局部最小为 arr[mid]

注意:

  • 注意数组为空,长度为 1,以及其他边界情况
  • 思路中 2,3 步的依据就是,先有 1 中段边界判断,所以一定有两端元素大于其紧邻元素(arr[0]>arr[1]arr[n-1]>arr[n-2])。数组要么一直递减到边界的紧邻元素从而结束循环,要么在这个过程中遇到某个局部最小,所以一定是有解的。

循环有序数组最小值

题目见 MinValue

思路:循环有序数组截出一个连续的子数组还是循环有序的。在每次循环中进行一下判断:

  1. arr[lo] < arr[hi],说明子数组已经升序,直接返回 arr[lo]。 否则,说明数组不升序,进行下面的步骤
  2. arr[lo] > arr[mid],最小值出现在左半部分
  3. arr[lo] < arr[mid],最小值出现在右半部分(因为说明 arr[lo] ~ arr[mid] 是升序的)
  4. arr[lo] = arr[mid],最小值为第一个小于 arr[lo] 或者就是 arr[lo]本身

注意:

  • 注意可能有重复元素的问题,所以在遇到 arr[lo] = arr[mid] 时,需要遍历 lo ~ hi 之间的元素来找到最小值
  • 这里的左右指针更新需要注意,hi = midlo = mid,而不是 mid-1mid+1,因为不能漏掉元素

快速N次方

题目见 QuickPower

思路:求出 k 的 1,2,4,8....次方作为中间值 tmp,减少相乘的次数

  1. 每次把 N 右移一位,若该位为 1,则将结果乘以中间值 tmp
  2. 每次令中间值 tmp 等于自己的平方(对应于第一步中的位移操作)

注意:

  • 注意越界问题,按题目要求,求 mod 某个数后的结果

作者@brianway更多文章:个人网站 | CSDN | oschina

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部