/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 vote83 views1 answer
Super vs super()
Java
0 vote122 views2 answers
How to insert a char at n position java
Java
1 vote119 views1 answer
Convert string to list java 8
Java
0 vote165 views1 answer
How to extract image from server url and store it in a folder in java
Java
3 votes125 views1 answer
Spring bean xml configuration
Java
0 vote113 views1 answer
Separateur JMenu swing java
Java
1 vote116 views1 answer
Functional remove java
Java
3 votes123 views2 answers
Arraylist of arraylist
Java
0 vote131 views1 answer
Example of "this" : to invoke current class method
Java
0 vote140 views1 answer
Grava
Java