Find position of an element in a sorted array of infinite numbers

By | April 24, 2016

Find position of an element in a sorted array of infinite numbers

In this post we deal with the problem of finding position of an element in a given array which is sorted and has infinite numbers.

Find position of an element in a sorted array of infinite numbers Problem Statement

Given a sorted array of infinite numbers, we need to  search for an element in the array. Since it’s given to us in the question that the array is sorted, the first approach which clicks into mind is binary search, but the problem here is that we don’t know the exact size of array. The number of elements in the array is infinite and so we are unable to decide an upper bound.

Find position of an element in a sorted array of infinite numbers Problem Example

Let the input arr[] = { 24, 6, 12, 78, 45, 1, 34...}
Element to be found = 1
Output = Element found at index 5

Find position of an element in a sorted array of infinite numbers Problem Solution

We cannot solve the problem using binary search algorithm as explained above. If the array is infinite, that means we don’t have proper bounds to apply binary search. So in order to find position of key(the element whose position has to be found) , first we find bounds and then apply binary search algorithm.

Algorithm:

  1. Let low be pointing to 1st element and high pointing to 2nd element of array.
  2. Now compare key with high index element.
  3. If it is greater than high index element then copy high index in low index and double the high index.
  4. If it is smaller, then apply binary search on high and low indices found.

Find position of an element in a sorted array of infinite numbers Problem Solution code in C++ :

#include<bits/stdc++.h>
using namespace std;
 
// Simple binary search algorithm
int binarySearch(int arr[], int l, int h, int x)
{
    if (h>=l)
    {
        int mid = l + (h - l)/2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid-1, x);
        return binarySearch(arr, mid+1, h, x);
    }
    return -1;
}
 
/*Function takes an infinite size array and a key and 
  returns its position if found else -1.We don't know size
  of arr[] and we assume size to be infinite in this function.
  Therefore, there is no index out of bound checking*/
int findPos(int arr[], int key)
{
    int l = 0, h = 1;
    int val = arr[0];
 
    // Find h to do binary search
    while (val < key)
    {
        l = h;        // store previous high
        h = 2*h;      // double high index
        val = arr[h]; // update new val
    }
 
    /* at this point we have updated low and high indices,
        thus use binary search between them*/
    return binarySearch(arr, l, h, key);
}
 
// Driver program
int main()
{
    int arr[] = {3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170};
    /*We do not specify size as we assume array to be infinite*/
    int ans = findPos(arr, 10);
    if (ans==-1)
        cout << "Element not found";
    else
        cout << "Element found at index " << ans;
    return 0;
}

 Output:

Element found at index 4

Time Complexity : O(p)
Space Complexity:O(1)

Explanation of complexity:Let p be the position of element to be searched. Number of steps for finding high index ‘h’ is O(Log p). The value of ‘h’ must be less than 2*p. The number of elements between h/2 and h must be O(p). Therefore, time complexity of Binary Search step is also O(Log p) and overall time complexity is 2*O(Log p) which is O(Log p).