/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 vote320 views1 answer
Java code to get all leaf nodes of a xml
Java
0 vote355 views1 answer
Thymeleaf Request method 'POST' not supportedorg.springframework.web.HttpRequestMethodNotSupportedException: Request method 'POST' not supported
Java Spring
0 vote321 views1 answer
Java random number generator 6
Java
51 votes343 views6 answers
Java remove last character
Java
-1 vote321 views2 answers
Running Sum of 1d Array
Java
0 vote336 views1 answer
Key caracter from code java
Java
-2 votes337 views2 answers
How to find a word in string in java
Java
0 vote372 views1 answer
Timer tick java
Java
0 vote308 views1 answer
Algorithms - Max value
Java
3 votes358 views3 answers
Empty array java
Java