Binary Search without finding the length of an array in O(logN) — Interview question

Problem Statement

Find a function to find the positive integer(X) in the array A and write a program to find X(if X exists) in O(log N) time. The array of integers have the following properties:

1. The array is sorted is an ascending order
2. The array holds distinct integers (i.e. there are no repeating numbers)
3. The array is 1-indexed, i.e. the first element is stored in A[1] (not A[0])
4. However the length of the array, N, is unknown (i.e. you don’t know how long the array is and arrayName.length is not available to you). In short, you can not use the length of the array to apply binary search

Note — This problem attempts to simulate a big data scenario — a scenario where the number of elements in the array is so big that it won’t fit in memory all at once. Therefore, since the Array won’t fit in memory, it would be difficult for us to figure out exactly the length of the array.

Analysis

You need length of an array to apply binary search on it. But as per the problem statement, you can’t use array.length to find out the length of the array.

If you use a loop to find out the count of the elements, you end up with the time complexity of O(N) and there is a limit on the time complexity of O(logN).

Hint

Since the length of the array is unknown, an error “ArrayIndexOutOfBoundsException” is returned if you try to index into the array with an integer greater than N.

Solution

You will proceed by applying the binary search algorithm on sub-arrays. Instead of taking the “end” pointer of the array as the last element of it, make it second element of the array. “start” as it is(first element).

public static int getSubArray(int array[], int key)

Apply binary search, and increase “end” pinter to double the previous sub-array bound size after each unsuccessful attempt.

public static int binarySearch(int array[], int start, int end, int key)

Calculating mid index value using start and end pointer. This formula is used to avoid overflow for large value of int data type.

int mid = (start + end) >>> 1;

Suppose mid exceeds the array limit, you get “ArrayIndexOutOfBoundsException”. You need to handle the exception gracefully in order to keep it going and decrement the “end” pointer until you get a valid index.

public static int getValidEndIndex(int array[], int start, int end)

Below is full code to find out the integer X with time complexity of O(logN)

Happy Coding :)