InfiniteArray.java

package com.company;

public class InfiniteArray {
    public static void main(String[] args) {
        int[] arr = {3,5,7,10,34,56,757,44563,53475,34346346,346364346};
        int target = 10;
        System.out.println(ans(arr, target));
    }
    static int ans(int[] arr, int target) {
        //first find the range
        //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 newStart = end + 1;
            //double the box value
            end = (2 * newStart) + 1;
            start = newStart;
        }
        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 - start) / 2;

            if (target < arr[mid]) {
                end = mid - 1;
            } else if (target > arr[mid]) {
                start = mid + 1;
            } else {
                //answer is found
                return mid;
            }
        }
        return -1;
    }
}