Also why on earth would you care about this?
because:
a) You are trying to do search on a randomly rotated sorted array which is enormous
b) You are trying to prepare for technical whiteboard tests
c) You like puzzles
b) is probably the most likely.
In my case it’s a combination of b) and c).
I almost solved this on my own. I didn’t get it quite right, but my thought processes were not totally wrong, which is a nice change.
QUESTION:
Search in Rotated Array: Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.
Example
Input: find 5 in [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]
Output: 8 (the index of 5 in the array)
SOLUTION(S):
Firstly, you can just loop through the whole array, checking for the value.
That gets you O(n) time and O(1) space.
Drop that whiteboard marker, and stare at your interviewer with a look of pure intimidation.
Did it work?
No, they say they would like it to scale better than O(n).
Urgh. Who do they think they are.
Let’s mine the problem statement for clues:
- Array is sorted
- Array is rotated
Sorted you say… I think I smell a binary search coming on.
Demon/Gargoyle interviewer: ‘Excellent. Proceed minion’
If we can use binary search, we can cut the problem in half with each check, giving us a run time of O(log n)
Demon/Gargoyle interviewer: ‘CODE IT!!! MINION’
Hold up there, I haven’t got my tactics in place yet.
For binary search to work we have to be able to work on a sorted array.
Because our array has been rotated, we essentially have two sorted arrays:
[15, 16, 19, 20, 25]
[1, 3, 4, 5, 7, 10, 14]
We can do binary search on each of these individually just fine.
So if we find the ‘rotation point’ or whatever you want to call it, we can split the array and RECURSE LIKE OUR LIFE DEPENDS ON IT.
How we gonna find that rotation point?
Rotation point = ‘point in the array where the previous element is bigger than the next element’. i.e it is not sorted.
Could just loop through the array and check each element, but that erodes all of our good work, as we are just searching for an item in the array again so we go back to O(n).
Demon/Gargoyle interviewer: ‘WHAT ARE YOU THINKING MINION??? YOU MUST VERBALISE YOUR DEEPEST THOUGHTS TO ME’
Fuck this industry.
Maybe we can use recursion again/a version of binary search?
Then we can get back to cutting that problem in half. O(log n) for the win!
I have an idea. Look.
[15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]
The middle index is 6, with a value of 3 in it.
One half of our array when split by this middle element is not sorted:
[15, 16, 19, 20, 25, 1, 3]
The other half is sorted:
[3, 4, 5, 7, 10, 14]
We can figure out which half is sorted by comparing the middle element (3) with the left and right most elements respectively.
15 is not smaller than 3, so that half is not sorted.
3 is smaller than 14, so that half is sorted.
Now we know that our ‘rotation point’ is in the left half of our array, so forget about the right half, and RECURSE.
[15, 16, 19, 20, 25, 1, 3]
Middle is 20, left half is sorted, right half is not sorted, so rotation point is in right half. RECURSE.
[20, 25, 1, 3]
middle is 1, element before it is 25. IT IS OUT OF ORDER WE HAVE FOUND OUR ROTATION POINT IN LOGARITHMIC TIME DID YOU HEAR THAT YOU IMPASSIVE GARGOYLE FUCK YOU
Suhwheet.
The recipe:
1) Find the rotation point recursively in O(log(n)) time.
2) Do binary search on both halves in O(2 * log(n)) time.
3) Profit/dance with joy at your new O(3 * log(n)) => O(log n) running time.
There are definitely optimisations that can be made here.
But I’m going to move on with my life for now. Behold:
const findRotationPoint = (array: number[], left: number, right: number) => {
const middle = Math.floor((left + right) / 2);
// This element is out of order
if (array[middle - 1] > array[middle]) {
return middle;
}
// If the left half is sorted
if (array[left] <= array[middle]) {
// Check the right half - as left half is OK
return findRotationPoint(array, middle + 1, right);
} else {
// Check the left half because it is not sorted so must contain the rotation point
return findRotationPoint(array, left, middle - 1);
}
};
const searchRecursive = (
array: number[],
left: number,
right: number,
target: number
): number => {
// Target not in array
if (left > right) {
return -1;
}
const middle = Math.floor((left + right) / 2);
if (array[middle] === target) {
// We found the target!
return middle;
}
if (array[middle] < target) {
return searchRecursive(array, middle + 1, right, target);
} else {
return searchRecursive(array, left, middle - 1, target);
}
};
const search = (array: number[], target: number) => {
// Find rotation point
const rotationPoint = findRotationPoint(array, 0, array.length - 1);
// Check to left of rotation point
const leftResult = searchRecursive(array, 0, rotationPoint, target);
if (leftResult !== -1) {
// We found it!
return leftResult;
} else {
// Check to right of rotation point
return searchRecursive(array, rotationPoint, array.length - 1, target);
}
};