/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 vote184 views1 answer
Spring-boot java header appliacation/json constant
Java Spring
3 votes119 views3 answers
Java tutorial
Java
0 vote124 views1 answer
Debug cxf
Java
0 vote162 views1 answer
Can a java class have more than 108 constructors
Java
0 vote121 views1 answer
Multiple string java
Java
0 vote129 views1 answer
Convertir un float en int en java
Java
1 vote133 views1 answer
How to create new frame with java swing
Java
0 vote122 views1 answer
One line hashmap java
Java
4 votes233 views2 answers
Java read each lines in file
Java
0 vote112 views1 answer
Spring security not going to logout success urk
Java Spring