/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

3 votes241 views1 answer
Composition java
Java
1 vote215 views1 answer
Null checker on addAll java
Java
0 vote247 views1 answer
How to draw Bezier Curve in Android
Java
0 vote204 views1 answer
Where do you use overriding in framework
Java
55 votes206 views4 answers
How to get last element in java
Java
0 vote209 views1 answer
Java check if divisible
Java
1 vote220 views1 answer
Internal Exception: java.sql.SQLSyntaxErrorException: Table 'sql4409754.SEQUENCE' doesn't exist Error Code: 1146
Java
2 votes209 views3 answers
How to create java textfield which allow only numbers
Java
0 vote199 views1 answer
Private access modifiers
Java
0 vote295 views1 answer
Bad JNI version returned from JNI_OnLoad in
Java