本文对和 二分搜素 有关的常见算法基础题思路分类进行分析和总结，并以 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 某个数后的结果
