(C/C++)给定一个数组，前n个为有序整数，剩余元素为无穷，以

无穷数组，前n个元素是整数且有序，剩余元素为无穷。
设计算法，以一个整数x为输入，以logn时间复杂度找到其中一个位置，满足其上元素值为x。

思路

一开始没怎么看懂，后来查了一下即需要在二分查找前进行O(logn)复杂度的查找确定二分的范围。
先比较数组的A[0]元素，若不相等接下来比较A[1],A[2],A[4],A[8]…,若找到一个区间A[ 2^n-1]<x<A[2ⁿ ],再对这个区间进行折半查找操作。总的时间为O(logn)。
若查找过程中A[i]中的i>n,则抛出异常。

#include <iostream>
#include <exception>
#define MAX 255
#define NOFOUND -1
#define N 10
#define LENGTH  15
using namespace std;


int INDEX[] = { 1,2,3,4,5,6,7,8,9,10,MAX,MAX,MAX,MAX,MAX };

int BinarySearch(int begin, int end, int num) {
    if (begin == end && INDEX[begin] != num)
        return NOFOUND;
    int mid = (begin + end) / 2;
    if (INDEX[mid] == num)
        return mid;
    if (INDEX[mid] > num)
        return BinarySearch(begin, mid, num);
    return BinarySearch(mid + 1, end, num);
}

void showIndex(int* index, int length) {
    for (int i = 0; i < length; i++)
        cout << index[i] << " ";
    cout << "\n";
}


int main(void) {
    cout << "原数组：";
    showIndex(INDEX,LENGTH);
    int find;
    cout << "输入要查找的数:";
    cin >> find;
    int i = 1;
    int res = 0;
    if (INDEX[0] == find)
        res = 0;
    else {
        int temp = INDEX[i];
        while (temp < find) {
            try {
                i *= 2;
                temp = INDEX[i];
            }
            catch (exception& e)
            {
                cout << "exception: " << e.what() << endl;
            }
        }
        res = BinarySearch(i / 2, i, find);
    }
    cout << "位置在：" << res << endl;
    system("pause");
    return 0;
}