Modified Binary Search Problems

Question 1

Order-agnostic Binary Search

Given a sorted array of numbers, find if a given number ‘key’ is present in the array. Though we know that the array is sorted, we don’t know if it’s sorted in ascending or descending order. You should assume that the array can have duplicates.

Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.

Example 1
Input: [4, 6, 10], key = 10
Output: 2

Example 2
Input: [1, 2, 3, 4, 5, 6, 7], key = 5
Output: 4

Example 3
Input: [10, 6, 4], key = 10
Output: 0

Example 4
Input: [10, 6, 4], key = 4
Output: 2

Answer 1

Let’s assume start is pointing to the first index and end is pointing to the last index of the input array (let’s call it arr).

First, we will find the middle of start and end. An easy way to find the middle would be: middle=(start+end)/2.

Next, we will see if the ‘key’ is equal to the number at index middle. If it is equal we return middle as the required index.

If ‘key’ is not equal to number at index middle, we have to check two things:

If key < arr[middle], then we can conclude that the keywill be smaller than all the numbers after index middle as the array is sorted in the ascending order. Hence, we can reduce our search to end = mid - 1.

If key > arr[middle], then we can conclude that the key will be greater than all numbers before index middle as the array is sorted in the ascending order. Hence, we can reduce our search to start = mid + 1.

We will repeat steps 2-4 with new ranges of start to end. If at any time start becomes greater than end, this means that we can’t find the ‘key’ in the input array and we must return ‘-1’.

If the array is sorted in the descending order, we have to update the step 4 above as:

If key > arr[middle], then we can conclude that the key will be greater than all numbers after index middle as the array is sorted in the descending order. Hence, we can reduce our search to end = mid - 1.

If key < arr[middle], then we can conclude that the key will be smaller than all the numbers before index middle as the array is sorted in the descending order. Hence, we can reduce our search to start = mid + 1.

Finally, how can we figure out the sort order of the input array? We can compare the numbers pointed out by start and end index to find the sort order. If arr[start] < arr[end], it means that the numbers are sorted in ascending order otherwise they are sorted in the descending order.

Question 2

Ceiling of a Number

Given an array of numbers sorted in an ascending order, find the ceiling of a given number ‘key’. The ceiling of the ‘key’ will be the smallest element in the given array greater than or equal to the ‘key’.

Write a function to return the index of the ceiling of the ‘key’. If there isn’t any ceiling return -1.

Example 1
Input: [4, 6, 10], key = 6
Output: 1
Explanation: The smallest number greater than or equal to ‘6’ is ‘6’ having index ‘1’.

Example 2
Input: [1, 3, 8, 10, 15], key = 12
Output: 4
Explanation: The smallest number greater than or equal to ‘12’ is ‘15’ having index ‘4’.

Example 3
Input: [4, 6, 10], key = 17
Output: -1
Explanation: There is no number greater than or equal to ‘17’ in the given array.

Example 4
Input: [4, 6, 10], key = -1
Output: 0
Explanation: The smallest number greater than or equal to ‘-1’ is ‘4’ having index ‘0’.

Answer 2

This problem follows the Binary Search pattern. Since Binary Search helps us find a number in a sorted array efficiently, we can use a modified version of the Binary Search to find the ceiling of a number.

We can use a similar approach as discussed in Order-agnostic Binary Search. We will try to search for the ‘key’ in the given array. If we find the ‘key’, we return its index as the ceiling. If we can’t find the ‘key’, the next big number will be pointed out by the index start.

Since we are always adjusting our range to find the ‘key’, when we exit the loop, the start of our range will point to the smallest number greater than the ‘key’ as shown in the above picture.

We can add a check in the beginning to see if the ‘key’ is bigger than the biggest number in the input array. If so, we can return ‘-1’.

Since we are reducing the search range by half at every step, this means that the time complexity of our algorithm will be O(logN) where ‘N’ is the total elements in the given array.

The algorithm runs in constant space O(1).

Question 3

Next Letter

Given an array of lowercase letters sorted in ascending order, find the smallest letter in the given array greater than a given ‘key’.

Assume the given array is a circular list, which means that the last letter is assumed to be connected with the first letter. This also means that the smallest letter in the given array is greater than the last letter of the array and is also the first letter of the array.

Write a function to return the next letter of the given ‘key’.

Example 1
Input: [‘a’, ‘c’, ‘f’, ‘h’], key = ‘f’

Output: ‘h’

Explanation: The smallest letter greater than ‘f’ is ‘h’ in the given array.

Example 2
Input: [‘a’, ‘c’, ‘f’, ‘h’], key = ‘b’

Output: ‘c’

Explanation: The smallest letter greater than ‘b’ is ‘c’.

Example 3
Input: [‘a’, ‘c’, ‘f’, ‘h’], key = ‘m’

Output: ‘a’

Explanation: As the array is assumed to be circular, the smallest letter greater than ‘m’ is ‘a’.

Example 4
Input: [‘a’, ‘c’, ‘f’, ‘h’], key = ‘h’

Output: ‘a’

Explanation: As the array is assumed to be circular, the smallest letter greater than ‘h’ is ‘a’.

Answer 3

The problem follows the Binary Search pattern. Since Binary Search helps us find an element in a sorted array efficiently, we can use a modified version of it to find the next letter.

We can use a similar approach as discussed in Ceiling of a Number. There are a couple of differences though:

1. The array is considered circular, which means if the ‘key’ is bigger than the last letter of the array or if it is smaller than the first letter of the array, the key’s next letter will be the first letter of the array.
2. The other difference is that we have to find the next biggest letter which can’t be equal to the ‘key’. This means that we will ignore the case where key == arr[middle]. To handle this case, we can update our start range to start = middle +1.

In the end, instead of returning the element pointed out by start, we have to return the letter pointed out by start % array_length. This is needed because of point 2 discussed above. Imagine that the last letter of the array is equal to the ‘key’. In that case, we have to return the first letter of the input array.

Since, we are reducing the search range by half at every step, this means that the time complexity of our algorithm will be O(logN) where ‘N’ is the total elements in the given array.

The algorithm runs in constant space O(1).

Question 4

Number Range

Given an array of numbers sorted in ascending order, find the range of a given number ‘key’. The range of the ‘key’ will be the first and last position of the ‘key’ in the array.

Write a function to return the range of the ‘key’. If the ‘key’ is not present return [-1, -1].

Example 1
Input: [4, 6, 6, 6, 9], key = 6

Output: [1, 3]

Example 2
Input: [1, 3, 8, 10, 15], key = 10

Output: [3, 3]

Example 3
Input: [1, 3, 8, 10, 15], key = 12

Output: [-1, -1]

Answer 4

The problem follows the Binary Search pattern. Since Binary Search helps us find a number in a sorted array efficiently, we can use a modified version of the Binary Search to find the first and the last position of a number.

We can use a similar approach as discussed in Order-agnostic Binary Search. We will try to search for the ‘key’ in the given array; if the ‘key’ is found (i.e. key == arr[middle]) we have two options:

1. When trying to find the first position of the ‘key’, we can update end = middle - 1 to see if the key is present before middle.
2. When trying to find the last position of the ‘key’, we can update start = middle + 1 to see if the key is present after middle.

In both cases, we will keep track of the last position where we found the ‘key’. These positions will be the required range.

Since, we are reducing the search range by half at every step, this means that the time complexity of our algorithm will be O(logN) where ‘N’ is the total elements in the given array.

The algorithm runs in constant space O(1).

Question 5

Search in a Sorted Infinite Array

Given an infinite sorted array (or an array with unknown size), find if a given number ‘key’ is present in the array. Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.

Since it is not possible to define an array with infinite (unknown) size, you will be provided with an interface ArrayReader to read elements of the array. ArrayReader.get(index) will return the number at index; if the array’s size is smaller than the index, it will return Integer.MAX_VALUE.

Example 1
Input: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30], key = 16
Output: 6
Explanation: The key is present at index ‘6’ in the array.

Example 2
Input: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30], key = 11
Output: -1
Explanation: The key is not present in the array.

Example 3
Input: [1, 3, 8, 10, 15], key = 15
Output: 4
Explanation: The key is present at index ‘4’ in the array.

Example 4
Input: [1, 3, 8, 10, 15], key = 200
Output: -1
Explanation: The key is not present in the array.

Answer 5

The problem follows the Binary Search pattern. Since Binary Search helps us find a number in a sorted array efficiently, we can use a modified version of the Binary Search to find the ‘key’ in an infinite sorted array.

The only issue with applying binary search in this problem is that we don’t know the bounds of the array. To handle this situation, we will first find the proper bounds of the array where we can perform a binary search.

An efficient way to find the proper bounds is to start at the beginning of the array with the bound’s size as ‘1’ and exponentially increase the bound’s size (i.e., double it) until we find the bounds that can have the key.

There are two parts of the algorithm. In the first part, we keep increasing the bound’s size exponentially (double it every time) while searching for the proper bounds. Therefore, this step will take O(logN) assuming that the array will have maximum ‘N’ numbers. In the second step, we perform the binary search which will take O(logN), so the overall time complexity of our algorithm will be O(logN+logN) which is asymptotically equivalent to O(logN).

The algorithm runs in constant space O(1).

Question 6

Minimum Difference Element

Given an array of numbers sorted in ascending order, find the element in the array that has the minimum difference with the given ‘key’.

Example 1
Input: [4, 6, 10], key = 7
Output: 6
Explanation: The difference between the key ‘7’ and ‘6’ is minimum than any other number in the array

Example 2
Input: [4, 6, 10], key = 4
Output: 4

Example 3
Input: [1, 3, 8, 10, 15], key = 12
Output: 10

Example 4
Input: [4, 6, 10], key = 17
Output: 10

Answer 6

The problem follows the Binary Search pattern. Since Binary Search helps us find a number in a sorted array efficiently, we can use a modified version of the Binary Search to find the number that has the minimum difference with the given ‘key’.

We can use a similar approach as discussed in Order-agnostic Binary Search. We will try to search for the ‘key’ in the given array. If we find the ‘key’ we will return it as the minimum difference number. If we can’t find the ‘key’, (at the end of the loop) we can find the differences between the ‘key’ and the numbers pointed out by indices start and end, as these two numbers will be closest to the ‘key’. The number that gives minimum difference will be our required number.

Since, we are reducing the search range by half at every step, this means the time complexity of our algorithm will be O(logN) where ‘N’ is the total elements in the given array.

The algorithm runs in constant space O(1).

Question 7

Bitonic Array Maximum

Find the maximum value in a given Bitonic array. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array arr[i] != arr[i+1].

Example 1
Input: [1, 3, 8, 12, 4, 2]

Output: 12

Explanation: The maximum number in the input bitonic array is ‘12’.

Example 2
Input: [3, 8, 3, 1]

Output: 8

Example 3
Input: [1, 3, 8, 12]

Output: 12

Example 4
Input: [10, 9, 8]

Output: 10

Answer 7

A bitonic array is a sorted array; the only difference is that its first part is sorted in ascending order and the second part is sorted in descending order. We can use a similar approach as discussed in Order-agnostic Binary Search. Since no two consecutive numbers are same (as the array is monotonically increasing or decreasing), whenever we calculate the middle, we can compare the numbers pointed out by the index middle and middle+1 to find if we are in the ascending or the descending part. So:

1. If arr[middle] > arr[middle + 1], we are in the second (descending) part of the bitonic array. Therefore, our required number could either be pointed out by middle or will be before middle. This means we will be doing: end = middle.
2. If arr[middle] <= arr[middle + 1], we are in the first (ascending) part of the bitonic array. Therefore, the required number will be after middle. This means we will be doing: start = middle + 1.

We can break when start == end. Due to the two points mentioned above, both start and end will be pointing at the maximum number of the bitonic array.

Question 8

Search Bitonic Array

Given a Bitonic array, find if a given ‘key’ is present in it. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array arr[i] != arr[i+1].

Write a function to return the index of the ‘key’. If the ‘key’ is not present, return -1.

Example 1
Input: [1, 3, 8, 4, 3], key=4
Output: 3

Example 2
Input: [3, 8, 3, 1], key=8
Output: 1

Example 3
Input: [1, 3, 8, 12], key=12
Output: 3

Example 4
Input: [10, 9, 8], key=10
Output: 0

Answer 8

The problem follows the Binary Search pattern. Since Binary Search helps us efficiently find a number in a sorted array we can use a modified version of the Binary Search to find the ‘key’ in the bitonic array.

Here is how we can search in a bitonic array:

1. First, we can find the index of the maximum value of the bitonic array, similar to Bitonic Array Maximum. Let’s call the index of the maximum number maxIndex.
2. Now, we can break the array into two sub-arrays:
   
   • Array from index ‘0’ to maxIndex, sorted in ascending order.
   • Array from index maxIndex+1 to array_length-1, sorted in descending order.
3. We can then call Binary Search separately in these two arrays to search the ‘key’. We can use the same Order-agnostic Binary Search for searching.

Question 9

Search in Rotated Array

Given an array of numbers which is sorted in ascending order and also rotated by some arbitrary number, find if a given ‘key’ is present in it.

Write a function to return the index of the ‘key’ in the rotated array. If the ‘key’ is not present, return -1. You can assume that the given array does not have any duplicates.

Answer 9

The problem follows the Binary Search pattern. We can use a similar approach as discussed in Order-agnostic Binary Search and modify it similar to Search Bitonic Array to search for the ‘key’ in the rotated array.

After calculating the middle, we can compare the numbers at indices start and middle. This will give us two options:

1. If arr[start] <= arr[middle], the numbers from start to middle are sorted in ascending order.
2. Else, the numbers from middle+1 to end are sorted in ascending order.

Once we know which part of the array is sorted, it is easy to adjust our ranges. For example, if option-1 is true, we have two choices:

1. By comparing the ‘key’ with the numbers at index start and middle we can easily find out if the ‘key’ lies between indices start and middle; if it does, we can skip the second part => end = middle -1.
2. Else, we can skip the first part => start = middle + 1.

Since we are reducing the search range by half at every step, this means that the time complexity of our algorithm will be O(logN) where ‘N’ is the total elements in the given array.

The algorithm runs in constant space O(1).

Question 10

Rotation Count

Given an array of numbers which is sorted in ascending order and is rotated ‘k’ times around a pivot, find ‘k’.

You can assume that the array does not have any duplicates.

Example 1
Input: [10, 15, 1, 3, 8]

Output: 2

Explanation: The array has been rotated 2 times.

Example 2
Input: [4, 5, 7, 9, 10, -1, 2]

Output: 5

Explanation: The array has been rotated 5 times.

Answer 10

This problem follows the Binary Search pattern. We can use a similar strategy as discussed in Search in Rotated Array.

In this problem, actually, we are asked to find the index of the minimum element. The number of times the minimum element is moved to the right will be equal to the number of rotations. An interesting fact about the minimum element is that it is the only element in the given array which is smaller than its previous element. Since the array is sorted in ascending order, all other elements are bigger than their previous element.

After calculating the middle, we can compare the number at index middle with its previous and next number. This will give us two options:

1. If arr[middle] > arr[middle + 1], then the element at middle + 1 is the smallest.
2. If arr[middle - 1] > arr[middle], then the element at middle is the smallest.

To adjust the ranges we can follow the same approach as discussed in Search in Rotated Array. Comparing the numbers at indices start and middle will give us two options:

1. If arr[start] < arr[middle], the numbers from start to middle are sorted.
2. Else, the numbers from middle + 1 to end are sorted.

Since we are reducing the search range by half at every step, this means that the time complexity of our algorithm will be O(logN) where ‘N’ is the total elements in the given array.

The algorithm runs in constant space O(1).