- Questions
- 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.
- 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.
- 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’.
- Search infinite sorted array
- Given an array of numbers sorted in ascending order, find the element in the array that has the minimum difference with the given ‘key’.
- 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].
- 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.
- 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.
- 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: [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**

- First we need to determine the sort order. To do that, we check the first and last numbers and if first number is lesser than last, its in ascending order, else descending.
- Then we do a binary search to find the key.
- Since its not said which key to return in case of duplicates, we will return any key.

`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:

- Key is equal to a candidate element. In that case we return the index of the candidate.
- Candidate element is lesser than key and is such that there is no other element lesser than key. We can check for this case by: 2.1 When we encounter a candidate smaller than key, we check the next element. If the next element is greater than key, that is our solution. 2.2 If there is no next element, there is no solution.
- One thing to look out for is what happens if the key is smaller than the smallest element in the array. In that case, it will never find a candidate which can satisfy the condition and we can return index 0.

`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`

.

- So if
`key`

is smaller than`mid`

, the number must lie towards the left, else towards the right. - The next letter will be the position of
`low`

. Why? - Since, we are narrowing down our`low->high`

range, till`low>high`

,`low+1`

would be the "next" number. - However, this is a circular array, so if
`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.

- if
`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`

. - if
`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:

- If
`arr[mid] > arr[mid+1]`

, the we are in the decreasing range. - If
`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:

- Left side is sorted in ascending order.
- Right side is sorted in ascending order because of the rotation.

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)`