/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 vote299 views2 answers
Death calculator by date of birth make in java
Java
0 vote248 views2 answers
Array access in java
Java
0 vote235 views1 answer
Order ognostic binary search
Java
3 votes299 views1 answer
Java Polymorphism
Java
12 votes287 views3 answers
Go to activity android
Java
0 vote277 views1 answer
Java print 2d char array
Java
0 vote271 views1 answer
Java string split underscore
Java
0 vote286 views1 answer
How to Compile the source code in ./src folder with libraries in ./lib folder using JavaSE-1.7
Java
0 vote276 views1 answer
Print 1 to 10 using thread in java
Java
0 vote284 views1 answer
Handle customized popup in selenium
Java