LeetCode Search in Rotated Sorted Array: Binary Search and Practical Improvements

Overview

Binary Search is adopted to solve LeetCode Search in Rotated Sorted Array problem with tricky part explained, improvements to make code compact and efficient.

Problem Definition

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution and Analysis

If there is no duplicates in the array, then the binary search approach sill works similarly here. The observation is that, after rotation, there is still one increasing interval and another rotated interval. If we know which interval is strictly increasing, then we can test whether the target is in this increasing interval or not. If so, we perform binary search again in this increasing interval, otherwise, we do the binary search in the other half rotated interval. Use i and j points to the left most element and the right most element in that array. Here is how to determine the increasing interval: Get the mid = (i+j) /2. Determine the increasing half interval by comparing Array[i] with and Array[mid]. Since every time, we can prune half the search space, the total time complexity would be O(log N). Based on this algorithm, here is the basic dirty code accepted by the LeetCode OJ, and I will try to point out several other improvement details to make it even more compact and efficient:

int search(int A[], int n, int target) {
    int lo = 0, hi = n - 1;
    int mid = 0;
    int rightSideSorted = 0;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (A[mid] < A[hi])
            rightSideSorted = 1;
        else
            rightSideSorted = 0;
        if (A[mid] == target)
            return mid;
        else if (A[mid] < target) {
            if (rightSideSorted) {
                if (target <= A[hi])
                    lo = mid + 1;
                else
                    hi = mid - 1;
            }
            else  {
                lo = mid + 1;
            }
        }
        else {
            if (rightSideSorted) {
                hi = mid - 1;
            }
            else  {
                if (target < A[lo])
                    lo = mid + 1;
                else
                    hi = mid - 1;
            }
        }
    }
    return -1;
}

Practical Improvements (More Compact Code)

(1) The source code above is a bit tedious, eventually, there are only 4 cases, the target is in the left sorted portion, right sorted portion, left rotated portion, right rotated portion, this indicates we do not need 6 if branches like the above, here comes a more compact code, just replace the if statement (6 cases) above with the following one:

if (rightSideSorted && A[mid] < target && target <= A[hi])
            lo = mid + 1;
        else if (!rightSideSorted && target < A[mid] && target >= A[lo])
            hi = mid - 1;
        else if (rightSideSorted)
            hi = mid - 1;
        else
            lo = mid + 1;

(2) To make the code more efficient, if we find the target is in the sorted portion, then we shall directly adopt the regular classic binary search, this saves us the time we spend on determining the 4 different cases which is not necessary for the non-rotated sorted array. You might want to try to implement this one by yourself. And you might need recursive implementation.

Summary

I discussed Binary Search to solve LeetCode Search in Rotated Sorted Array problem with tricky part explained and several improvements including less cases judgement, mix classic binary search to help are given to make the code more compact and efficient.

Written on May 16, 2013