Search in Rotated Sorted Array

ID: 62; medium; 搜索旋转排序数组

Solution 1 (Java)

public class Solution {
    /**
     * @param A: an integer rotated sorted array
     * @param target: an integer to be searched
     * @return: an integer
     */
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) return -1;
        int left = 0, right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) return mid;

            // mid element on the left half
            if (A[mid] > A[left]) {
                if (target >= A[left] && target < A[mid]) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
                // mid element on the right half
                if (target > A[mid] && target <= A[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }
        if (A[left] == target) return left;
        if (A[right] == target) return right;
        return -1;
    }
}

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

The 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].

  1. If target and the mid element are on the same half (target is on the left half), we can discard the right half of the array.

  2. 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

If 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).

  1. If target and the mid element are on the same half (target is on the right half), we can discard the left half of the array.

  2. 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, 5, 6, 7]

4

7

5

[4, 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