Open In App

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

Last Updated : 18 Mar, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Suppose you have a sorted array of infinite numbers, how would you search an element in the array?
Source: Amazon Interview Experience. 
Since array is sorted, the first thing clicks into mind is binary search, but the problem here is that we don’t know size of array. 
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, first we find bounds and then apply binary search algorithm.
Let low be pointing to 1st element and high pointing to 2nd element of array, Now compare key with high index element, 
->if it is greater than high index element then copy high index in low index and double the high index. 
->if it is smaller, then apply binary search on high and low indices found. 
 

Below are implementations of above algorithm
 

C++




// C++ program to demonstrate working of an algorithm that finds
// an element in an array of infinite size
#include<bits/stdc++.h>
using namespace std;
 
// Simple binary search algorithm
int binarySearch(int arr[], int l, int r, int x)
{
    if (r>=l)
    {
        int mid = l + (r - l)/2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid-1, x);
        return binarySearch(arr, mid+1, r, x);
    }
    return -1;
}
 
// function takes an infinite size array and a key to be
//  searched and returns its position if found else -1.
// We don't know size of arr[] and we can assume size to be
// infinite in this function.
// NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE
// 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};
    int ans = findPos(arr, 10);
    if (ans==-1)
        cout << "Element not found";
    else
        cout << "Element found at index " << ans;
    return 0;
}


Java




// Java program to demonstrate working of
// an algorithm that finds an element in an
// array of infinite size
 
class Test
{
    // Simple binary search algorithm
    static int binarySearch(int arr[], int l, int r, int x)
    {
        if (r>=l)
        {
            int mid = l + (r - l)/2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binarySearch(arr, l, mid-1, x);
            return binarySearch(arr, mid+1, r, x);
        }
        return -1;
    }
     
    // Method takes an infinite size array and a key to be
    // searched and returns its position if found else -1.
    // We don't know size of arr[] and we can assume size to be
    // infinite in this function.
    // NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE
    // THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING
    static 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
            //check that 2*h doesn't exceeds array
            //length to prevent ArrayOutOfBoundException
            if(2*h < arr.length-1)
               h = 2*h;            
            else
               h = arr.length-1;
             
            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 method to test the above function
    public static void main(String[] args)
    {
        int arr[] = new int[]{3, 5, 7, 9, 10, 90,
                            100, 130, 140, 160, 170};
        int ans = findPos(arr,10);
         
        if (ans==-1)
            System.out.println("Element not found");
        else
            System.out.println("Element found at index " + ans);
    }
}


Python3




# Python Program to demonstrate working of an algorithm that finds
# an element in an array of infinite size
 
# Binary search algorithm implementation
def binary_search(arr,l,r,x):
 
    if r >= l:
        mid = l+(r-l)//2
 
        if arr[mid] == x:
            return mid
 
        if arr[mid] > x:
            return binary_search(arr,l,mid-1,x)
 
        return binary_search(arr,mid+1,r,x)
 
    return -1
 
# function takes an infinite size array and a key to be
# searched and returns its position if found else -1.
# We don't know size of a[] and we can assume size to be
# infinite in this function.
# NOTE THAT THIS FUNCTION ASSUMES a[] TO BE OF INFINITE SIZE
# THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING
def findPos(a, key):
 
    l, h, val = 0, 1, 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 binary_search(a, l, h, key)
 
# Driver function
arr = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170]
ans = findPos(arr,10)
if ans == -1:
    print ("Element not found")
else:
    print("Element found at index",ans)


C#




// C# program to demonstrate working of an
// algorithm that finds an element in an
// array of infinite size
using System;
 
class GFG {
     
    // Simple binary search algorithm
    static int binarySearch(int []arr, int l,
                                int r, int x)
    {
        if (r >= l)
        {
            int mid = l + (r - l)/2;
             
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binarySearch(arr, l,
                                   mid-1, x);
                                    
            return binarySearch(arr, mid+1,
                                       r, x);
        }
         
        return -1;
    }
     
    // Method takes an infinite size array
    // and a key to be searched and returns
    // its position if found else -1. We
    // don't know size of arr[] and we can
    // assume size to be infinite in this
    // function.
    // NOTE THAT THIS FUNCTION ASSUMES
    // arr[] TO BE OF INFINITE SIZE
    // THEREFORE, THERE IS NO INDEX OUT
    // OF BOUND CHECKING
    static 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 method to test the above
    // function
    public static void Main()
    {
        int []arr = new int[]{3, 5, 7, 9,
            10, 90, 100, 130, 140, 160, 170};
        int ans = findPos(arr, 10);
         
        if (ans == -1)
            Console.Write("Element not found");
        else
            Console.Write("Element found at "
                            + "index " + ans);
    }
}
 
// This code is contributed by nitin mittal.


PHP




<?php
// PHP program to demonstrate working
// of an algorithm that finds an
// element in an array of infinite size
 
// Simple binary search algorithm
function binarySearch($arr, $l,
                      $r, $x)
{
    if ($r >= $l)
    {
        $mid = $l + ($r - $l)/2;
        if ($arr[$mid] == $x)
            return $mid;
        if ($arr[$mid] > $x)
            return binarySearch($arr, $l,
                           $mid - 1, $x);
        return binarySearch($arr, $mid + 1,
                                   $r, $x);
    }
    return -1;
}
 
// function takes an infinite
// size array and a key to be
// searched and returns its
// position if found else -1.
// We don't know size of arr[]
// and we can assume size to be
// infinite in this function.
// NOTE THAT THIS FUNCTION ASSUMES
// arr[] TO BE OF INFINITE SIZE
// THEREFORE, THERE IS NO INDEX
// OUT OF BOUND CHECKING
function findPos( $arr, $key)
{
    $l = 0; $h = 1;
    $val = $arr[0];
 
    // Find h to do binary search
    while ($val < $key)
    {
         
        // store previous high
        $l = $h;    
         
         // double high index
        $h = 2 * $h;
         
        // update new val
        $val = $arr[$h];
    }
 
    // at this point we have
    // updated low and high
    // indices, Thus use binary
    // search between them
    return binarySearch($arr, $l,
                        $h, $key);
}
 
    // Driver Code
    $arr = array(3, 5, 7, 9, 10, 90, 100,
                 130, 140, 160, 170);
    $ans = findPos($arr, 10);
    if ($ans==-1)
        echo "Element not found";
    else
        echo "Element found at index " , $ans;
 
// This code is contributed by anuj_67.
?>


Javascript




<script>
// JavaScript program to demonstrate working of an algorithm that finds
// an element in an array of infinite size
 
// Simple binary search algorithm
function binarySearch(arr, l, r, x)
{
    if (r>=l)
    {
        let mid = l + Math.floor((r - l)/2);
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid-1, x);
        return binarySearch(arr, mid+1, r, x);
    }
    return -1;
}
 
// function takes an infinite size array and a key to be
// searched and returns its position if found else -1.
// We don't know size of arr[] and we can assume size to be
// infinite in this function.
// NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE
// THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING
function findPos(arr, key)
{
    let l = 0, h = 1;
    let 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
    let arr = [3, 5, 7, 9, 10, 90, 100, 130,
                            140, 160, 170];
    let ans = findPos(arr, 10);
    if (ans==-1)
        document.write("Element not found");
    else
        document.write("Element found at index " + ans);
 
 
 
// This code is contributed by Surbhi Tyagi.
</script>


Output

Element found at index 4

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).

 

Approach: The problem can be solved based on the following observation: 

  • Since array is sorted we apply binary search but the length of array is infinite so that we take start = 0 and end = 1 .
  • After that check value of target is greater than the value at end index,if it is true then change newStart = end + 1  and newEnd = end +(end – start +1)*2 and apply binary search .
  • Otherwise , apply binary search in the old index values.

Below are implementations of above algorithm:
 

C++




// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Simple binary search algorithm
int binarySearch(int arr[], int target, int start, int end)
{
    while (start <= end) {
 
        int mid = start + (end - start) / 2;
 
        if (target < arr[mid]) {
            end = mid - 1;
        }
        else if (target > arr[mid]) {
            start = mid + 1;
        }
        else {
            // ans found
            return mid;
        }
    }
    return -1;
}
 
 
// an algorithm that finds an element in an
// array of infinite size
 
int findPos(int arr[], int target)
{
    // first find the range
    // first start with a box of size 2
    int start = 0;
    int end = 1;
 
    // condition for the target to lie in the range
    while (target > arr[end]) {
        int temp = end + 1; // this is my new start
        // double the box value
        // end = previous end + sizeofbox*2
        end = end + (end - start + 1) * 2;
        start = temp;
    }
    return binarySearch(arr, target, start, end);
}
 
// Driver code
int main()
{
 
    int arr[]
        = { 3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170 };
    int target = 10;
    // Function call
    int ans = findPos(arr, target);
    if (ans == -1)
        cout << "Element not found";
    else
        cout << "Element found at index " << ans;
 
    return 0;
}


Java




// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
// Java program to demonstrate working of
// an algorithm that finds an element in an
// array of infinite size
 
public class GFG {
 
    static int findPos(int[] arr, int target)
    {
        // first find the range
        // first start with a box of size 2
        int start = 0;
        int end = 1;
 
        // condition for the target to lie in the range
        while (target > arr[end]) {
            int temp = end + 1; // this is my new start
            // double the box value
            // end = previous end + sizeofbox*2
            end = end + (end - start + 1) * 2;
            start = temp;
        }
        return binarySearch(arr, target, start, end);
    }
    static int binarySearch(int[] arr, int target,
                            int start, int end)
    {
        while (start <= end) {
            // find the middle element
            //            int mid = (start + end) / 2; //
            //            might be possible that (start +
            //            end) exceeds the range of int in
            //            java
            int mid = start + (end - start) / 2;
 
            if (target < arr[mid]) {
                end = mid - 1;
            }
            else if (target > arr[mid]) {
                start = mid + 1;
            }
            else {
                // ans found
                return mid;
            }
        }
        return -1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 3,   5,   7,   9,   10, 90,
                      100, 130, 140, 160, 170 };
        int target = 10;
        // Function call
        int ans = findPos(arr, target);
        if (ans == -1)
            System.out.println("Element not found");
        else
            System.out.println("Element found at index "
                               + ans);
    }
}


Python3




# Python program to demonstrate working of
# an algorithm that finds an element in an
# array of infinite size
 
import sys
 
def findPos(arr, target):
    # first find the range
    # first start with a box of size 2
    start = 0
    end = 1
 
    # condition for the target to lie in the range
    while target > arr[end]:
        temp = end + 1  # this is my new start
        # double the box value
        # end = previous end + sizeofbox*2
        end = end + (end - start + 1) * 2
        start = temp
    return binarySearch(arr, target, start, end)
 
def binarySearch(arr, target, start, end):
    while start <= end:
        # find the middle element
        #            int mid = (start + end) / 2; //
        #            might be possible that (start +
        #            end) exceeds the range of int in
        #            java
        mid = start + (end - start) // 2
 
        if target < arr[mid]:
            end = mid - 1
        elif target > arr[mid]:
            start = mid + 1
        else:
            # ans found
            return mid
    return -1
 
# Driver code
if __name__ == '__main__':
    arr = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170]
    target = 10
    # Function call
    ans = findPos(arr, target)
    if ans == -1:
        print("Element not found")
    else:
        print("Element found at index", ans)


Javascript




<script>
 
 // Javascript  code to implement the approach
 
// an algorithm that finds an element in an
// array of infinite size
function findPos( arr,  target)
    {
        // first find the range
        // first start with a box of size 2
        let start = 0;
        let end = 1;
 
        // condition for the target to lie in the range
        while (target > arr[end]) {
            let temp = end + 1; // this is my new start
            // double the box value
            // end = previous end + sizeofbox*2
            end = end + (end - start + 1) * 2;
            start = temp;
        }
        return binarySearch(arr, target, start, end);
    }
// Simple binary search algorithm
function binarySearch(arr, target, start, end)
{
    while (start <= end) {
 
        let mid = start + Math.floor((end - start) / 2);
 
        if (target < arr[mid]) {
            end = mid - 1;
        }
        else if (target > arr[mid]) {
            start = mid + 1;
        }
        else {
            // ans found
            return mid;
        }
    }
    return -1;
}   
// Driver code
    let arr = [3, 5, 7, 9, 10, 90, 100, 130,
                            140, 160, 170];
// Function call                           
    let ans = findPos(arr, 10);
    if (ans==-1)
        document.write("Element not found");
    else
        document.write("Element found at index " + ans);
     
 
</script>


C#




// C# code to implement the approach
 
using System;
 
class GFG
{
static int FindPos(int[] arr, int target)
{
// First find the range
// First start with a box of size 2
int start = 0;
int end = 1;
    // Condition for the target to lie in the range
    while (target > arr[end])
    {
        int temp = end + 1; // This is my new start
        // Double the box value
        // End = previous end + sizeofbox*2
        end = end + (end - start + 1) * 2;
        start = temp;
    }
    return BinarySearch(arr, target, start, end);
}
 
static int BinarySearch(int[] arr, int target, int start, int end)
{
    while (start <= end)
    {
        // Find the middle element
        //            int mid = (start + end) / 2; //
        //            might be possible that (start +
        //            end) exceeds the range of int in
        //            java
        int mid = start + (end - start) / 2;
 
        if (target < arr[mid])
        {
            end = mid - 1;
        }
        else if (target > arr[mid])
        {
            start = mid + 1;
        }
        else
        {
            // ans found
            return mid;
        }
    }
    return -1;
}
 
// Driver code
public static void Main()
{
    int[] arr = { 3,   5,   7,   9,   10, 90,
                  100, 130, 140, 160, 170 };
    int target = 10;
    // Function call
    int ans = FindPos(arr, target);
    if (ans == -1)
        Console.WriteLine("Element not found");
    else
        Console.WriteLine("Element found at index "
                           + ans);
}
}


Output

Element found at index 4

Time Complexity: O(logN) 
Auxiliary Space: O(1)



Previous Article
Next Article

Similar Reads

Find Nth item distributed from infinite items of infinite types based on given conditions
Given a positive integer N, the task is to find the Nth item given out when there are infinite items of the infinite number of types such that the items are given out in the following fashion: Day 1: 1 item of Type-I are given out.Day 2: 2 items of the Type-II and 1 item of Type-I are given out.Day 3: 3 items of the Type-III, 2 items of the Type-II
10 min read
Find the position of given element N in infinite spiral matrix starting from top-left
Given a number N and an infinite 2D matrix, which is to be filled using the algorithm given below, the task is to find the coordinates of the given element present in the matrix. The algorithm is as follows: The leftmost and topmost cell of the matrix is filled with 1. Then, all the cells are filled with consecutive numbers starting from 2The leftm
6 min read
Find the index of first 1 in an infinite sorted array of 0s and 1s
Given an infinite sorted array consisting 0s and 1s. The problem is to find the index of first ‘1’ in that array. As the array is infinite, therefore it is guaranteed that number '1' will be present in the array. Examples: Input : arr[] = {0, 0, 1, 1, 1, 1} Output : 2 Input : arr[] = {1, 1, 1, 1,, 1, 1} Output : 0 Approach: The problem is closely r
9 min read
Count of right shifts for each array element to be in its sorted position
Given an array arr[] of size N that contains elements from the range [1, N], the task is to calculate the number of right shifts required for each element to reach its respective position if the array was sorted.Examples: Input: arr[] = {1, 4, 3, 2, 5}, N = 5 Output: 0 2 0 3 0 Explanation: The sorted array is {1, 2, 3, 4, 5}. 4 is at index 1, so ri
5 min read
Count N-digit numbers such that every position is divisible by the digit at that position
Given a positive integer N, the task is to count the number of N-digit numbers such that every index (1-based indexing) in the number is divisible by the digit occurring at that index. Since the court can be very large, print it modulo 109 + 7. Examples: Input: N = 2Output: 2Explanation: The numbers 11 and 12 are the only 2-digit numbers satisfying
6 min read
Find the count of unvisited indices in an infinite array
Given an array of infinite length and two integers M and N which are co-primes, the task is to find the number of positions that cannot be visited starting from the first position when in a single move from arr[i], either arr[i + M] or arr[i + N] can be reached. Note that the result is always finite.Examples: Input: M = 2, N = 5 Output: 2 From inde
6 min read
Find missing element in a sorted array of consecutive numbers
Given an array arr[] of n distinct integers. Elements are placed sequentially in ascending order with one element missing. The task is to find the missing element.Examples: Input: arr[] = {1, 2, 4, 5, 6, 7, 8, 9} Output: 3Input: arr[] = {-4, -3, -1, 0, 1, 2} Output: -2Input: arr[] = {1, 2, 3, 4} Output: -1 No element is missing. Principles: Look fo
7 min read
Find the sum of infinite series 1^2.x^0 + 2^2.x^1 + 3^2.x^2 + 4^2.x^3 +.......
Given an infinite series and a value x, the task is to find its sum. Below is the infinite series 1^2*x^0 + 2^2*x^1 + 3^2*x^2 + 4^2*x^3 +....... upto infinity, where x belongs to (-1, 1) Examples: Input: x = 0.5 Output: 12 Input: x = 0.9 Output: 1900 Approach:Though the given series is not an Arithmetico-Geometric series, however, the differences [
3 min read
Find if the given number is present in the infinite sequence or not
Given three integers A, B and C. In an infinite sequence, A is the first number, C is the common difference (Si - Si - 1 = C). The task is to check if the number B will appear in the sequence or not.Examples: Input: A = 1, B = 7, C = 3 Output: Yes The sequence will be 1, 4, 7, 10, ...Input: A = 1, B = -4, C = 5 Output: No Approach: There are two ca
4 min read
Find the color of given node in an infinite binary tree
Given an infinitely long binary tree having a pattern as below: 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ ...................... Also given an array arr of size N and a number K. The task is to color all the subtrees of node arr[i] with colour i (1 &lt;= i &lt;= N) one after another. Find the colour of node K after colouring all subtrees. Note:- In
8 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg