Find position of an element in an Infinite Sorted Array

Question:

You are given an array in sorted order, but it is infinite. You are also given an key element. You need to check if the element is present in that infinite array.

array = {1, 2, 3, 4, 5, 7, 8, 9, 10, 100, 200, 300}
key = 8

Element is found at index 2.

Solution:

We can apply binary search.

But to apply binary search, we know the start index i.e 0. But we also need to get the end index.

As the array is infinite, how will you find the end index?

Let us understand how we get the end index with the help of an example:

Suppose you have the infinite array {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …} and you need to find the element 8.

Initially we assign index 0 as start index and index 1 as end index.

Then we check, if the key value is greater than the value at end index,

if it is greater then we double the end index and assign previous end index as start index.

We continue this step till we find an element that is greater than the key element.

Then we apply simple binary search.

Example:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}

Start index = 0
End index = 1

8 > arr[1] => 8 > 2 true
So start index = 1
end index = 1 * 2 = 2

Again check 8 > arr[2] => 8 > 3 true
So start index = 2
end index = 2 * 2 = 4

Again check 8 > arr[4] => 9 > 5 true
So start index = 4
end index = 4 * 2 = 8

Again check 8 > arr[8] => 8 > 9 false

Now we got start index as 4 and end index as 8.

Apply binary search between that index

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

Output:

The key 5 is found at index 4