Search in Rotated Sorted Array
ID: 62; medium; 搜索旋转排序数组
Solution 1 (Java)
Notes
In order to perform a classical binary search, we need to have a strictly increasing or decreasing series. Here, the rotate array can be seen as two increasing arrays. We need to determine which half we should perform the operations on. Thus, we compare the mid
element with the first element in the array to see which half the mid
element is on currently.
I. The mid
element is on the left half
mid
element is on the left halfThe reason is that if the mid
element is larger than the first element, by the construction of the rotated array, we know that the mid
element is on the left half now. After this first check, we try to see where target
is. We compare if the target
is on the same half (left half) as the mid element. This comparison is simple checking if target
is in between A[left]
and A[mid]
.
If
target
and themid
element are on the same half (target
is on the left half), we can discard the right half of the array.If they are on different halves (
target
is on the right half), we can discard the left half.
II. The mid
element is on the right half
mid
element is on the right halfIf the mid
element is smaller than the first element, then it is on the right half. Similarly, we try to see where target
is. If target
is in between A[mid]
and A[right]
, then target
is on the same half as the mid
element (right half).
If
target
and themid
element are on the same half (target
is on the right half), we can discard the left half of the array.If they are on different halves (
target
is on the left half), we can discard the right half.
Example
[4, 5, 6, 7, 0, 1, 2]
and target = 5
left  right  mid  New Range 
4  2  7 

4  7  5 

Case I. 1.: The mid
element and target
are both on the left side. Loop terminates, the index of 5 is returned.
Last updated