/Java/Position of an element in infinite sorted array

Position of an element in infinite sorted array

public class InfiniteArray {
  /*
  as the given array is infinite size, we need to find the range,
  where the target element lies.
  we exponentially double the size and checks if the target element greater
  than the array[end]. if true we return the boundaries as new start and end.
  */
  
    public static int[] FindRange(int[] array, int target) {
        int[] ranges = new int[2];
        int start = 0;
        int end = 1;
        while (target > array[end]) {
            int newStart = end+1;
            end = end + (end-start+1)*2;
            start = newStart;
        }
        ranges[0] = start;
        ranges[1] = end;
        return ranges;
    }
    public static int BinarySearch(int[] array, int target) {
        int[] rangeArray = FindRange(array, target);
        int start = rangeArray[0];
        int end = rangeArray[1];

        while (start <= end) {
            int mid = start + (end-start) / 2;
            if (array[mid] < target) start = mid+1;
            else end = mid-1;
            if (array[mid] == target) return mid;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] list  = new int[]{3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170};
        System.out.println(BinarySearch(list, 10)); // Output: 4
    }
}

Similar codes

0 vote203 views1 answer
Huffman coding in Java
Java
2 votes211 views2 answers
Java stream order by property
Java
-1 vote213 views1 answer
Spring boot hibernate log sql
Java
-2 votes183 views1 answer
Java create new empty list
Java
2 votes192 views2 answers
Find Numbers with Even Number of Digits
Java
7 votes262 views1 answer
Solid principles in programming
Java
0 vote210 views1 answer
Mint menu disapeared
Java
1 vote193 views1 answer
Java Multiple Interfaces
Java
0 vote209 views1 answer
Binomial heap implementation java
Java
0 vote228 views1 answer
How to check size of arrayin java
Java