/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 vote229 views1 answer
How to get the length of a jagged array java
Java
0 vote224 views1 answer
Spring core xml configuration for collection using constructor
Java
0 vote243 views1 answer
How to put string in char array in java tutorialspoint
Java
2 votes229 views1 answer
Add digits java
Java
0 vote250 views1 answer
Console java
Java
0 vote253 views1 answer
UserRedirectRequiredException: A redirect is required to get the users approval spring boot 5 security
Java
0 vote240 views1 answer
Create thread
Java
1 vote273 views2 answers
Bukkit runnable
Java
0 vote248 views1 answer
Guess the number java
Java
3 votes221 views1 answer
How to add negative random numbers in java
Java