【设n个不同的整数排好序后存于T[1..n]中，若存在一个下标i（1≤ i ≤ n），使得T[i]=i。试设计一个有效算法找到这个下标，要求算法在最坏情形下的计算时间为O(log n)】转自http://zmp1123.blog.163.com/blog/static/1193291592013314581911/
设n 个不同整数排好序后存于T[0:n-1]中，若存在一个下标i，0≤i＜n，是的T[i]=i，设计一个有效地算法找到这个下标。要求算法在
最坏情况下的计算时间为O(logn)。
算法描述如下：
由于n 个整数是不同的，因此对任意0≤i＜n-1 有T[i]≤T[i+1]-1。
1 对于0＜i＜n，当T[i]>i 时，对任意的i≤j≤n-2 有T[j]≥T[i]+j-i>i+j-i=j。
2 对于0＜i＜n,当T[i]＜i 时，对任意的0≤j≤i 有T[j]≤T[i] -i+j ＜i-i +j =j。
由①和②可知，用二分搜索法可以在O(logn)时间内找到所要的下标。
算法如下：
非递归二分搜索：
Template
int binarySearch(T a[],int left,int right)
{
int middle;
while(left<=right){
middle=(left+right)/2;
//middle=(left+right)>>1;
if(middle==a[middle]) return middle;
if(middle>a[middle]) left=middle+1;
else right=middle-1;
}
return 0;
}
递归二分搜索：
Template
int FindFixedPoint(T a[],int left,int right)
{
int middle;
middle=(left+right)/2;
//middle=(left+right)>>1;
if(left<=right){
if(middle==a[middle]) return middle;
else if(middle>a[middle]) FindFixedPoint(a,middle+1,right);
else FindFixedPoint(a,left,middle-1);
}
return 0;
}
推荐阅读
- 集合的全排列（Java实现）
- 算法导论学习笔记——2.3.1分治法——习题2-4逆序对数
- 拓展欧几里得算法详解
- 算法导论程序15-计数排序（Python）
- 算法导论 — 8.3 基数排序
- 算法导论程序16--基数排序（Python）
- 算法导论 基数排序
- RSA模重复平方算法小示例
- 【算法导论之四】计数排序
- 算法导论计数排序实现