第二章 笔记与练习题

2.4.4 折半查找（binary search）

定义：给一个整数X 和一个有序的数组A[]，求下标 i 使得 A[i] = X ，如果X 不在数据中则返回 -1；

在一个有序数组arr中,寻找一个数target 在 数组 arr 中的位置（索引）。如果未找到返回 -1；

首先找到数组的中心位置midIndex，比较target 数 与中间数arr[midIndex]的大小，若target 比arr[midIndex] 数大表明 该数在目前数组的右半部分，缩小查找范围lowIndex = midIndex + 1;若target比arr[midIndex] 数小，表明该数在目前数组的左半部分，缩小查找范围highIndex = midIndex - 1;显然程序执行的次数是小于数组的长度（每次都是从数组的一半节点开始寻找）所折半查找的时间复杂度是应该O(logN) N 为数组长度。

欧几里得算法：

gcdV2() 方法是 用迭代写法与gcd 结果一样。

定理2.1: 如果m > n,则m mod n < m/2

幂运算：

计算 X^n 的明显算法是使用N-1的乘法自乘 n ≤ 1 是这种递归的基准情形，否则，若n 是偶数，我们有X^n = X^n/2 * X^n/2, 如果 n 是奇数，则X^n = X^(n-1)/2 * X^(n-1)/2 *X;