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
Implementation: OrderAgnosticBinarySearch
O(logn)
O(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'.
Implementation: CeilingOfNumber
There are two conditions here:
O(logn)
O(1)
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'.
Implementation: NextLetter
key = 'f'
0 1 2 3
'a' 'c' 'f' 'h'
l m h
mid = 0 + (3-0)/2 = 1
key >= arr[mid], low = mid+1
0 1 2 3
'a' 'c' 'f' 'h'
l h
m
mid = 2 + (3-2) / 2 = 2
key >= arr[mid], low = mid+1
0 1 2 3
'a' 'c' 'f' 'h'
l / h
m
mid = 3 + (3-3) / 2 = 3
key < arr[mid], high = mid-1 (2)
loop terminates, because low > high
We have to find the smallest number which is greater than key.
key is smaller than mid, the number must lie towards the left, else towards the right.low. Why? - Since, we are narrowing down our low->high range, till low>high, low+1 would be the "next" number.low was the last element index=arr.length-1, it would overflow the array. Thus, we mod it, so it return index 0.O(logn)
O(1)
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.
Implementation: SearchSortedInfiniteArray
Here, the issue with doing binary search is we dont know the high, since there could be an infinite amount of numbers. Since we dont know, its reasonable to start with either a random number or a really high number.
Once we start with a number, then we follow regular binary search till we either get the key or run out of numbers.
This can be optimized if we knew the distribution of the numbers, but since that's not the case, a random number is as good as any.
O(logn)
O(1)
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
Implementation: MinDiffElement
If the key is present in the array, then that number is the one with the minimum difference of 0. If we dont, then the low and high positions are the two candidates for the min. We will return whichever has the min diff.
O(logn)
O(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
Implementation: BitonicArrayMax
There are 2 parts to the bitonic array: an ascending part and a descending part.
arr[mid] > arr[mid+1], that means we are in the descending part. If we are in the descending part, the max element is either mid or an element to the left of mid.arr[mid] < arr[mid+1], we are in the ascending part. Then, the max element must be to the right of mid.O(logn)
O(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
Implementation: SearchBitonicArray
Based on the previous problem, we know:
arr[mid] > arr[mid+1], the we are in the decreasing range.arr[mid] < arr[mid+1], we are in the increasing range.Based on which range we are in, we then, can move low and high to either left or right of mid.
O(logn)
O(1)
Example 1:
Input: [10, 15, 1, 3, 8], key = 15
Output: 1
Explanation: '15' is present in the array at index '1'.
Example 2:
Input: [4, 5, 7, 9, 10, -1, 2], key = 10
Output: 4
Explanation: '10' is present in the array at index '4'.
Implementation: SearchRotatedArray
When we select a mid, one of two things can happen:
We can check this by comparing low to mid. If low is <= mid, then from low to mid, aka, the left side is in ascending order.
Else, since the left side is not in ascending order, and because there can be only one rotation, the right side must be in ascending order.
Based on the value of key and mid, we can now move our low and high accordingly.
O(logn)
O(1)
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.
Example 3:
Input: [1, 3, 8, 10]
Output: 0
Explanation: The array has been not been rotated.
Implementation: RotationCount
What does rotation mean? For this array
[10, 15, 1, 3, 8]
The sorted variant would be:
[1, 3, 8, 10, 15]
To move, 10 and 15 to index 0 and 1 respectively, we would need to make 2 movements.
For
[4, 5, 7, 9, 10, -1, 2]
The sorted array is:
[-1, 2, 4, 5, 7, 9, 10]
We have to move 4, 5, 7, 9, 10, aka, 5 numbers to get to the current set of rotations.
In other words, if we substract the number of elements that are in the original order (without rotation) from the length of the array, we will get the number of rotated elements, aka, the number of rotations.
How do we do that?
We need to find an element whose next element is less than the current element. That element must me the start of non-rotated elements.
We can do a regular binary search and if mid > mid+1, mid+1 must be the start of non-rotated sub-array.
O(logn)
O(1)