/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

31 votes356 views5 answers
Java how to get current time
Java
0 vote381 views1 answer
Java for item in array
Java
1 vote367 views1 answer
Java check if able to parse int
Java
1 vote354 views1 answer
Xlint:deprecation android studio
Java
0 vote390 views1 answer
Offsetdattime to date
Java
0 vote359 views1 answer
Spring websocket allow origin
Java
0 vote361 views1 answer
Java 8 stream option
Java
0 vote351 views1 answer
Java suppresswarnings unchecked
Java
0 vote364 views1 answer
Most common exceptions in java
Java
0 vote347 views1 answer
How to iterate list of string array in java
Java