Searching a rotated array in Swift
Recently I made post about rotating a sorted array.
It is then rotated by k elements (to the left by 4 in the following example).
Brute force
Linear search — this will take a running time of O(n), with a possible implementation below:
Doing better
If we know the split point, we could rotate and then perform a binary search on the elements:
O(n + log n)
It’s the same runtime O(n) but shows insight to the problem.
If we know k…
We can perform a binary search on each half of the list.
Finding k in log n time
A sorted array looks something like this:
To put it simply: the graph “goes up”.
Our target array does not do that, however:
The gray line represents the first split. Those elements on the right of the array that are greater than k have been split. We can use this information to perform a binary search modification to find k.
That is, we are at the kth element if the element to the right is less than the current one, or nil. We know if the kth element is to the left of the current search term if it is “below the line”, and to the right if it is “above the line”.
Implementation
We can run a simple binary search twice
Obviously if we find our target in the first half, we can stop.
Here is a sample call for the first half:
binarySearch(arr, 14, 0, k)
Can we do better?
Can’t we create a custom binary search where the two halves of the array do not have to be within the same physical array?
We’d have to create mapping functions:
We will also need a true modulus operator like:
Then we can modify the binary search to use the mapping and the helper function:
Which can be called with the following that represents the following ordered array 3,5,6,7,9,12,14 which is split at location 4 (k) to give 7,9,12,14,3,5,6. We can look for 12, and expect our function to return true.
let arrMapped = [7,9,12,14,3,5,6]
binarySearchMapped(arr: arrMapped, target: 12, k: 4)
Why would we do this?
Mapping binary search in this way is tricky, but shows understanding of algorithms in use here.
