/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

5 votes133 views1 answer
How to get an array as input in java
Java
0 vote136 views1 answer
Log10 in java
Java
1 vote133 views2 answers
Android java navigation bar show icon with title
Java
0 vote147 views1 answer
Treemap java entryset
Java
1 vote160 views1 answer
@SpringBootApplication
Java Spring
2 votes152 views1 answer
For loop in multidimensional array java
Java
-1 vote142 views2 answers
Java Arrays method
Java
0 vote139 views2 answers
Hibernate onetone with mapsid
Java
2 votes128 views1 answer
Install java 8 on windows 10
Java
1 vote124 views1 answer
Space seperator in string in java
Java