题目二：
2.16给定一个无穷数组A[.]，其中前n个元素都是整数，且已经排好序，剩余元素均为∞。n的值未知。给出一个算法，以一个整数x为输入，以O(logn)时间找到数组中的一个位置，并满足其上的元素为x。
算法思想：
从题目所给时间复杂度开始思考，结合题目要求是查找算法，自然想到二分查找，时间复杂度为O（logn），但此题并未告知数组长度，所以要确定二分查找的范围，如果用循环遍历，则需要O（n）时间，O（n）+O（logn）=O（n），不满足题目所需，所以这里在遍历时采用i2=i代替i++进行遍历，这样时间复杂度就由O(n)降为O（logn），具体来说找上限时就是X与A[i]比较，若X大，则X再与A[i2]比较，找下限时同理与A[i/2]比较。找到范围后采用二分查找即可。时间复杂度为O(logn)+O(logn)=O(logn)。**
代码：
#include <iostream>
#include <vector>
#include <math.h>
#define INFINITY 1000000
using namespace std;
int BiSearch(vector<int>&A, int low, int high, int k)
{
if (low > high)
return -1;
else
{
int mid = (low + high) / 2;
if (A[mid] == k)
return mid;
else
{
if (A[mid] < k)
return BiSearch(A, mid + 1, high, k);
else
return BiSearch(A, low, mid - 1, k);
}
}
}
int main(void)
{
vector<int>A(INFINITY, INFINITY);
int n = 100;
for (int i = n; i > 0; i--)
{
A.insert(A.begin(), i);
}
int x;
cin >> x;
if (x == A[0])
cout << "位置为0";
else
{
int fre_high = 0,fre_low=0,i=1;
while (i>=1)
{
if (x > A[i])
{
i *= 2;
fre_high++;
}
fre_low = fre_high;
if (x < A[i])
{
i /= 2;
fre_low--;
}
if (x >= A[pow(2, fre_low)] && x <= A[pow(2, fre_high)])
{
break;
}
}
if (i == 0)
cout << "x不在序列中";
else
cout<<"位置为："<<BiSearch(A, pow(2, fre_low), pow(2, fre_high), x);
}
system("pause");
return 0;
}
