Binary Search

Find the position of an element in a sorted infinite array

Rajeev SinghAlgorithms1 mins read

Find the position of an element in a sorted infinite array

Search in a sorted infinite array

Given an infinite sorted array (or an array with unknown size), find if a given target value is present in the array. Write a function to return the index of the target if it is present in the array, otherwise return -1.

Example 1:

Input: [2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28. 32, 35], target = 16
Output: 7
Explanation: The target is present at index '7' in the array.

Example 2:

Input: [2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28. 32, 35], target = 19
Output: -1
Explanation: The target not present in the array

Binary Search to Find the position of an element in a sorted infinite array

Given that the array is sorted, we can apply binary search to find the element. The only problem is that the array is infinite so we don’t know the bounds of the array.

We will first try to find the bounds of the array within which the target might lie and then perform binary search.

An efficient way to find the lower and upper bounds is to start at the beginning of the array with the lower bound at the 1st element (start=0) and the upper bound at the 2nd element (end=1).

  • If the target value is greater than the upper bound (target > a[end]), then set the lower bound to the current upper bound and increase the upper bound exponentially (i.e. double it).
  • Otherwise, apply binary search on the current lower bound (start) and upper bound (end).

Let’s look at the implementation:

import java.util.Scanner;

class FindElementInSortedInfiniteArray {
    private static int binarySearch(int[] a, int target) {
        int start = 0;
        int end = 1;

        // First try to find the lower and upper bounds before applying binary search
        while (target > a[end]) {
            start = end;
            end *= 2;
        }

        while (start <= end) {
            int mid = (start + end) / 2;

            if (target == a[mid]) {
                return mid;
            } else if (target < a[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }
        int target = keyboard.nextInt();
        keyboard.close();

        System.out.printf("BinarySearch(%d) = %d%n", target, binarySearch(a, target));
    }
}