查找元素在无限排序数组中的位置

题：

系统会按排序顺序为您提供一个数组，但它是无限的。您还将获得一个关键要素。您需要检查该无限数组中是否存在该元素。

数组= {1,2,3,4,5,7,8,9,10,100,200,300}
键= 8

元素位于索引2。

解：

我们可以应用二进制搜索。

但是要应用二进制搜索，我们知道开始索引，即0。但是，我们还需要获取结束索引。

由于数组是无限的，您将如何找到结束索引？

让我们借助示例了解如何获取结束索引：

假设您拥有无限数组{1、2、3、4、5、6、7、8、9、10，…}，您需要找到元素8。

最初，我们将索引0指定为开始索引，将索引1指定为结束索引。

然后，我们检查键值是否大于结束索引处的值，

如果更大，则我们将结束索引加倍，并将先前的结束索引分配为开始索引。

我们继续此步骤，直到找到一个大于关键元素的元素。

然后，我们应用简单的二进制搜索。

例：
{1、2、3、4、5、6、7、8、9、10，…}

起始索引= 0
结束索引= 1

8 > arr[1] => 8 > 2 true
因此开始索引= 1
结束索引= 1 * 2 = 2

再次检查8> arr[2] => 8 > 3 true
因此开始索引= 2
结束索引= 2 * 2 = 4

再次检查8> arr[4] => 9 > 5 true
因此开始索引= 4
结束索引= 4 * 2 = 8

再次检查8> arr[8] => 8 > 9 false

现在我们开始索引为4，结束索引为8。

在该索引之间应用二进制搜索

C ++解决方案

#include <iostream>
using namespace std;

int binary_search(int arr[], int start, int end, int key) 
{ 
    while (start <= end) 
    { 
        int mid = start + (end - start) / 2; 
  
          if (arr[mid] == key) 
            return mid; 
  
          if (arr[mid] < key) 
            start = mid + 1; 
  
          else
            end = mid - 1; 
    } 
  
    return -1; 
} 

int get_end_index(int arr[], int key) 
{ 
    int start = 0;
    int end = 1; 
    int val = arr[0]; 
  
    while (val < key) 
    { 
        start = end; // store previous end index 
        end = 2*end; // double end index
        val = arr[end]; // update new val for next iteration
    } 
    
    // now we got start and end index, perform normal binary search
    return binary_search(arr, start, end, key); 
} 


int main(void) 
{ 
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    int key = 5;

    int result = get_end_index(arr, key);

    cout<<" The key "<< key <<" is found at index " <<result<<endl;

    return 0; 
} 

输出：

The key 5 is found at index 4