4.5 二分法

4.5.1 二分查找

对于严格递增没有重复元素的序列查找。

int binarySearch(int A[],int left, int right, int x){//A[]严格递增数组，x为要查找的数//返回x在A中的位置int mid;while(left <= right){ //否则left>right,形成不了区间mid = (left+right)/2;if(A[mid]==x) return mid;else if(A[mid]>x)right = mid - 1; //往左区间[left,mid-1]查找elseleft = mid + 1; //往右区间[mid+1,right]查找}return -1; //查找失败
}

接下来考虑在有重复元素递增序列的查找。

1、我们要求查找元素x在此序列中第一次出现的位置。

int binarySearch(int A[],int left, int right, int x){//A[]有重复元素递增数组，x为要查找的数//返回x在A中第一次出现的位置int mid;while(left < right){ mid = (left+right)/2;if(A[mid]==x) right = mid; //等于x的元素在x的位置或者往左else if(A[mid]>x)right = mid; elseleft = mid + 1; //x还在右边，往右区间[mid+1,right]查找}return left；
}

不同之处在于 A[mid]==x) 时，往左边查找，最后返回left。

2、我们要求查找大于元素x的元素在此序列中第一次出现的位置。

int binarySearch(int A[],int left, int right, int x){//A[]有重复元素递增数组，x为要查找的数//返回大于x的元素第一次出现的位置int mid;while(left < right){ mid = (left+right)/2;if(A[mid]==x) left = mid+1; //大于x的元素还在x的右边，所以往右查找else if(A[mid]>x)right = mid; elseleft = mid + 1; //往右区间[mid+1,right]查找}return left；
}

4.5.2 快速幂/二分幂

计算 aba^bab 的二分法，基于以下思想：

1. 如果b为奇数，ab=a×ab−1a^b=a\times a^{b-1}ab=a×ab−1；
2. 如果b为偶数，ab=ab2×ab2a^b=a^{\frac{b}{2}} \times a^{\frac{b}{2}}ab=a2b​×a2b​ 。