題目二：

2.16給定一個無窮數(shù)組A[.]，其中前n個元素都是整數(shù)，且已經(jīng)排好序，剩余元素均為∞。n的值未知。給出一個算法，以一個整數(shù)x為輸入，以O(logn)時間找到數(shù)組中的一個位置，并滿足其上的元素為x。

算法思想：

從題目所給時間復雜度開始思考，結合題目要求是查找算法，自然想到二分查找，時間復雜度為O（logn），但此題并未告知數(shù)組長度，所以要確定二分查找的范圍，如果用循環(huán)遍歷，則需要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;
}