/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 vote219 views1 answer
Java read first line of file
Java
0 vote219 views1 answer
Flink prometheus alert on failed jobs
Java
0 vote227 views1 answer
Vscode code formatter cannot format
Java
0 vote240 views1 answer
Timer tick java
Java
3 votes222 views1 answer
Ocha in japanese
Java
0 vote205 views1 answer
How to remove all characters after a certain character from a string in java
Java
0 vote211 views3 answers
Number Formating in java
Java
0 vote247 views1 answer
Android:windowLightStatusBar programmatically
Java
0 vote258 views1 answer
Database springboot
Java Spring
1 vote221 views1 answer
Java get system line separator
Java