This is a detailed explanation of the “Search in Rotated Sorted Array” problem on Leetcode. The problem isn’t complicated, but because of the combinametrics involved, it has some nice symmetries that you might only see when you work out the problem fully.
In an ordinary binary search, the side of the array we choose next depends on how the target and the midpoint fall relative to each other. There are only two possibilities:
|-----m-----| |-----m-----|
t t
^Search left ^Search right
Here m represents the middle and t the target.
In the rotated problem, we introduce another variable: The array’s still sorted, but it’s rotated by an unknown amount, so the largest element of the array can be anywhere. The side that we decide to search depends on the configuration of these elements. If you just follow the same rule as before, there are cases where you’ll choose the wrong side to search:
|-----m--|t-|
^Search left!
“|” represents the largest element of the array
Ignoring the cases where one or more of the values equal another, there are 3! = 6 possible orderings of those three elements:
0) |-t---m---|-|
1) |-|---m---t-|
2) |-----m--t|-|
3) |-----m--|t-|
4) |-|t--m-----|
5) |-t|--m-----|
We can include the other cases by grouping them into cases 0-5 as appropriate. We can ignore the case where t=m, since we’ve just found the answer. Then, the cases where t=| fall into cases 2-5, and the cases where m=| fall into 0, 1, 3, or 5. The diagram below shows that:
m=| t=|
0) |-t---m---|-| |-t---|-----|
1) |-|---m---t-| |-----|---t-|
2) |-----m--t|-| |-----m---|-|
3) |-----m--|t-| |-----|---t-| |-----m---|-|
4) |-|t--m-----| |-|---m-----|
5) |-t|--m-----| |-t---|-----| |-|---m-----|
We would like to choose the side where t falls, but we have to work from what we know. We can begin by dividing the above into two categories: cases where t<m and where t>m. These are, respectively, 0,3,4 and 1,2,5.
We can distinguish between these cases by instead considering the magnitude of the rightmost element of the array, r, relative to t and m. This diagram shows that, marking the side we search with an arrow (--->):
t<m t>m
0) |-t---m---|-| r < t, m 1) |-|---m---t-| r < t, m
<------ ------>
3) |-----m--|t-| t < r < m 2) |-----m--t|-|
------> ------>
4) |-|t--m-----| t,m < r 5) |-t|--m-----| m < r < r
<------ <------
The important cases here are 3) and 5), since the direction we search. Notice how the two conditions are inverses of each other – in the t<m case (3) we have t <= r < m and we search the right side, and in the t>m case (5) we have m <= r < t and search the left side. The equals sign comes from whichever of t or m is closer to r, as with considering the m=| or t=| cases. This leads to the following solution:
class RotatedSearch(object):
def __init__(self, nums, target):
self.nums = nums
self.target = target
def search(self, lo, hi):
# Base cases
if (hi - lo) == 0:
return -1
if (hi - lo) == 1:
if self.nums[lo] == self.target:
return lo
else:
return -1
# Recursive cases
mid = lo + (hi - lo)/2
xm = self.nums[mid]
xr = self.nums[hi -1]
if xm == self.target:
return mid
if xm < self.target:
if (xr < self.target) and (xr >= xm):
return self.search(lo, mid)
else:
return self.search(mid, hi)
else:
if (xr >= self.target) and (xr < xm):
return self.search(mid, hi)
else:
return self.search(lo, mid)
The solution below makes a further simplification, effectively treating 3) as a special case of t>m and 5) as a special case of t<m. This reduces the conditions to the same as that of a binary search:
int search(vector<int>& nums, int target) {
int lo = 0, hi = nums.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
double num = (nums[mid] < nums[0]) == (target < nums[0])
? nums[mid]
: target < nums[0] ? -INFINITY : INFINITY;
if (num < target)
lo = mid + 1;
else if (num > target)
hi = mid;
else
return mid;
}
return -1;
}