Given a rotated sorted array, how can I find the largest value in that array?

Question

I have given this a lot of thought and was unable to find the most optimal solution. I am preparing for technical interviews, but I haven't found very much stuff related to this question. My first step was to implement a naive O(n) algorithm that searches through the entire array to find the maximum integer. Now I know I can do much better than this, so I thought maybe there was a way to use Binary Search or take advantage of the fact that at least one half of the array is fully sorted. Maybe you could find the middle value and compare it to the start and end of the array.

Example:

[5, 7, 11, 1, 3] would return 11.

[7, 9, 15, 1, 3] would return 15.

Answer 1

In a sorted array (even rotated), you can be sure to use binary search (O(log2(n)).

/**
* Time complexity: O(log2(n))
* Space complexity: O(1)
*
* @param nums
* @return
*/
public int findMax(int[] nums) {
        // binary search
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[left] < nums[mid]) {
                left = mid;
            } else if (nums[left] > nums[mid]) {
                right = mid - 1;
            } else {    
                // subtility here if there are duplicate elements in the array.
                // shift the left linearly
                left = left + 1;
            }
        }
        return nums[left];
    }

Answer 2

Use modified binary search to eliminate half the sorted subarray (if there are two sorted subarrays remove the "lower" subarray) in each step while keeping track of a potentially updated maximum.

#include <iostream>
#include <cstdlib>
#include <vector>

int main(int argc, char** argv)
{   
    std::vector<int> nums;
    for(int i = 1; i < argc; i++)
        nums.push_back(atoi(argv[i]));

    int start = 0;
    int end = argc - 2;
    int max = nums[start];
    while(start <= end) {
        int mid = (start + end) >> 1;
        int cand;
        if(nums[start] <= nums[mid])  {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
        cand = nums[mid];
        if(cand > max)
           max = cand;
    }
    std::cout << max << std::endl;
    return 0;
}