You're probably familiar with how to do binary search on a regular sorted array. But what happens if that array is in a different order?

In this video, you'll learn how to do a binary search on a sorted array that is rotated.

Transcript

Cool. So the question here is that we have an array. A simple sorted array would be like 1, 2, 3, 4, 5, 6. We hopefully know how to do binary search in an array like this. We're going to look at the middle. We're going to see, okay, is the value that we're looking for larger or smaller than that value, and then if it's smaller, we would look at this subarray, et cetera, et cetera. So that part's pretty straight forward.

But in this case, we're actually taking the array and we're rotating. So we're saying, okay, let me lop off – let's say these two values at the end – and I'm going to rotate them to the beginning. So I have 5, 6 1, 2, 3, 4. And the question becomes, well, how do we find a value in this array? And how do we do a binary search when the array is not actually in at least completely sorted order, right? The sections are sorted, but the whole thing is not sorted.

And this is where we have to ask… the best way to think about this is to ask, what are we actually doing when we do binary search? Because a lot of times when we're doing binary search, we're thinking about it as I'm going to go left if it's smaller, right if it's bigger. That is one specific version of binary search.

More generally what we're doing when we do binary search, is we're just asking the question: Can I do some sort of constant time calculation to determine whether my result is in the left subarray or the right subarray? And it doesn't necessarily have to be it's larger or smaller. If we had an array that was in reverse order, we could also do binary search on that.

We would just do the opposite, even though it's not as simple as that original problem. And in this same case, what we want to do is we want to ask that question, which is: how do we determine, or can we determine in constant time whether our value is in the right subarray or the left subarray? Because if we can do that, then doing the binary search is easy. If we know which half of our array to look in, then doing the rest of the binary search is not that hard. And so when we think about this, we end up with a couple of different options.

So like, let's say that we're, I don't know, let's say that we're looking for six. And so we're going to look in the middle and now what we find is that, okay, well, six is larger than two, so if this array wasn't rotated, then it would be in this subarray, but because the array is rotated, the six has been rotated around to over here. And so the question is, how do we know what that rotation is? Well, or how do we know which subarray?

So in this case, the way that we want to, the way that we approach this is by looking at the entire range, because we know a couple of things. One is that if I look at this value and I look at this value, if this lower value is less than this higher value, then that means that this entire subarray is not rotated. If the lower index value is less than the higher index value, then this section of array is not rotated because if it were rotated, then the larger value would have been moved to this end of the subarray.

So in that case then we know, because what we really want to know again is, does six go into this range? And if we look at this lower end value, and we look at this upper end value, and we know that it's not rotated, then we know that because six is less than the upper end value, it's not in that subarray.

On the other hand, the opposite problem that we run into is let's say that we look at the subarray on the other side. If we look at this subarray and we look at the first and last value… in this case, we see that this value, the five, is greater than the two. So a value in the lower index is larger than a value of the higher index.

And that means that there is a rotation in this array. So the question is what values can be contained within this subarray? And the answer is any value that is greater than five – because it starts at five and goes up from here. And also any value that is less than two, because anything greater than two and less than five should, based on our understanding of this, be ending up in this subarray over here.

Now, using that, we now can figure out, okay, does our value have to be in the left subarray or the right subarray? By looking at the range of a sub-array, we know two things: we know, one, whether there was a rotation in that subarray or not; and, two, we know what the range of possible values are.

So basically what we end up in this case is that our left subarray X has to be greater than five or X has to be less than two. And our right subarray, the values in here, is going to be between two and five. So two is less than X, which is less than five.

And these are mutual. I mean, I'm not, I'm not worrying about the specifics of the bounds, but these are going to be mutually exclusive. So since they're mutually exclusive, now we know which side our value has to be.

As long as we can reduce our problem to two mutually exclusive sets, basically. And we understand like this subarray is the one set and that subarray the other set, doesn't really matter what our data is at all. It's just a matter of, is it in the left side or is it on the right side?

If you enjoyed this video, check out one of our recent videos on the eight algorithms that you need to know for your coding interviews.