/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 vote373 views1 answer
Java program to find perimeter of rectangle
Java
1 vote335 views1 answer
Dexter dependency
Java
0 vote332 views1 answer
Java iterator to stream
Java
0 vote332 views1 answer
ClassNotFoundException: org.springframework.ui.freemarker.FreeMarkerConfigurationFactory
Java
0 vote319 views1 answer
Java comment vérifier une égalité de String
Java
1 vote313 views1 answer
How to read a .json from web api java
Java
5 votes375 views2 answers
How to add elements in array in java using for loop
Java
0 vote320 views1 answer
Sorting boolean array with prime index
Java
6 votes341 views2 answers
Java get files in directory
Java
135 votes525 views6 answers
Java random number generator
Java