LeetCode Find Minimum in Rotated Sorted Array: Binary Search, Tricky Boundary Issue

Overview

Binary search algorithm is used to solve LeetCode Find Minimum in Rotated Sorted Array. Tricky details (boundary determination ) are discussed to clarify things.

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

Find the minimum element.

You may assume no duplicate exists in the array.

Solution and Analysis

Binary search is easy to come into our mind for solving such a problem. Yes indeed, the correct algorithm is binary search and is quite similar to the one I have discussed in my old post: “LeetCode Search in Rotated Sorted Array: Binary Search and Practical Improvements“.

The only thing is that as is probably known to all, the implementation could be very tricky. I first give the accepted source by LeetCode OJ for this problem Find Minimum in Rotated Sorted Array, and then I will point it out that the tricky part you need to pay attention to:

int findMin(vector<int> &num) {
    int n = num.size();
    if (n <= 0) return -1;
    int lo = 0, hi = n - 1;
    int mid = 0;

    while (lo < hi - 1) {
        if (num[lo] <= num[hi])
            return num[lo];
        mid = lo + (hi - lo) / 2;
        if (num[lo] <= num[mid])
            lo = mid;
        else
            hi = mid;
    }
    if (lo == hi) return num[lo];
    if (hi > lo)  return min(num[lo], num[hi]);
    return -1;
}

So the key observation is that, the minimum would be in the rotated half, if the whole sequence is rotated, otherwise, the minimum is just the first element since the whole sequence is sorted. And several tricks in the code:

  • (1) set lo or hi to mid, rather than mid – 1 or mid + 1, since the mid one could possibly be the minimum
  • (2) the while loop condition is important, otherwise, the while might be infinite loop (why?)
  • (3) a useful suggestion is that come up with some simple test cases by yourself before you really head into coding

Summary

Binary search algorithm is used to solve LeetCode Find Minimum in Rotated Sorted Array. Tricky details (boundary determination) are discussed to clarify things a bit more.

Written on November 14, 2014