2.16给定一个无穷数组A[.]，其中前n个元素都是整数，且已经

题目二：

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;
}