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;