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

You have to binary search in a clever way to achieve a O(lg n) bound. Observe that the element to the right of the max element is the min (or none if the array is not rotated at all). So do a regular binary search but check that the element at index mid is the max, if not compare the first and last elements in each of the left/right subarrays. If first<last in the left subarray, you know that the left subarray is sorted and go right, otherwise you go left.

Let's assume that array is called a and it has n elements.

/* check if not rotated at all */
int ans = INFINITY;
if(a[0] < a[n-1] || n == 1)
{   ans = a[n-1];
    return;
}

/* array is certainly rotated */
int l = 0, r = n-1;
while(r - l > 5)
{   int m = (l + r) / 2;
    if(a[m] > a[m+1]) { ans = a[m]; break; }
    else
    {   if(a[l] < a[m-1]) l = m+1;
        else r = m-1;
    }
}

/* check the remaining elements (at most 5) in a loop */
if(ans == INFINITY)
{   for(int i = l; i <= r; i++)
    {   ans = max(ans, a[i]);
    }
}

I've not tested this code. The reason i break when the number of elements is 5 or less is to be sure that number of elements in either subarray is at least 2 (so you can be sure that first and last are not the same element). You've got to try this yourself and fix it if there is anything to fix. Hope this helps.

Answer 3

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;
}

Answer 4

Leetcode accepted answer

Condition - (array is sorted, it is rotated) -

Searching for a max element in sorted rotated array in a long length array is little bit easy but we have to consider the edge cases which are the reason why maximum code answers fail at end. Approach is similar to binary search but edge cases are different

Case 1: when array is of size 2. we can directly return max or min element from the array.

Case 2: When we return our start index, we should always double check if it is greater than the start+1 element as when we return start index we usually increase it by size one and it returns the element which is not the greatest.

Code for this:

public static int findMax(int[] nums) {
        // binary search
        int start = 0;
        int end = nums.length - 1;
        // if array length is 2 then directly compare and return max element
        if(nums.length == 2){
            return nums[0] > nums[1] ? 0 : 1;
        }

        while (start < end) {
            // finding mid element
            int mid = start + (end - start) / 2;
            // checking if mid-element is greater than start
            // then start can become mid
            if (nums[start] < nums[mid]) {
                start = mid;
            }
            // checking if mid-element is smaller than start
            // then it can be ignored and end can become mid-1
            else if (nums[start] > nums[mid]) {
                end = mid - 1;
            }
            // now checking the edge case
            // we have start element which is neither smaller or greater than mid 
            // element
            // that means start index = mid-index
            // so we can increase start index by 1 if current start index is smaller 
            // that start +1
            // else the current start index is the max element
            else {
                if(nums[start]<=nums[start+1]) {
                    start = start + 1;
                }
                else {
                    return nums[start];
                }
            }
        }
        return nums[start];
    }

---

#binarySearch #rotatedArray #sortedArray #array

Answer 5

Question : find largest in the rotated sorted array.The array don't have any duplicates: Solution : Using Binary Search. The Idea : Always remember in a Sorted Rotated Array, the largest element will always be on the left side of the array. Similarly, the smallest element will always be on the right side of the array. The code is :

public class Test19 {

    public static void main(String[] args) {
        int[] a = { 5, 6, 1, 2, 3, 4 };
        System.out.println(findLargestElement(a));

    }

    private static int findLargestElement(int[] a) {

        int start = 0;
        int last = a.length - 1;

        while (start + 1 < last) {

            int mid = (last - start) / 2 + start;
            if (mid < start) {
                mid = start;
            }
            if (mid > start) {
                last = mid - 1;
            } else {
                mid--;
            }

        } // while

        if (a[start] > a[last]) {
            return a[start];
        } else
            return a[last];

    }

}

Answer 6

The solution I've come up with is both compact and efficient. It is basically a spin-off of the Binary Search Algorithm.

int maxFinder(int[] array, int start, int end)
  {
    //Compute the middle element
    int mid = (start + end) / 2;

    //return the first element if it's a single element array
    //OR
    //the boundary pair has been discovered.
    if(array.length == 1 || array[mid] > array[mid + 1])
    {return mid;}

    //Basic Binary Search implementation
    if(array[mid] < array[start])
    {return maxFinder(array, start, mid - 1);}
    else if(array[mid] > array[end])
    {return maxFinder(array, mid + 1, end);}

    //Return the last element if the array hasn't been rotated at all.
    else
    {return end;}
  }

Answer 7

Speaking of using binary search to solve this problem at a time complexity of O(log2n). I would do as the following

#include<stdio.h>
#define ARRSIZE 200 
int greatestElement(int* , int ) ;

int main()  {
    int arr[ARRSIZE] ; 
    int n ; 
    printf("Enter the number of elements you want to enter in the array!") ;
    scanf("%d" , &n) ;
    printf("Enter the array elements\n") ;
    for(int i = 0 ; i < n ; i++)    {
        scanf("%d", &arr[i]) ;
    }
    printf("%d is the maximum element of the given array\n",greatestElement(arr,n)) ;
}

int greatestElement(int* arr, int n)    {
    int mid = 0 ;
    int start = 0 , end = n-1 ;
    while(start < end)  {
        mid = (start+end)/2 ;
        if(mid < n-1 && arr[mid] >= arr[mid+1]) {
            return arr[mid] ;
        }
        if(arr[start] > arr[mid])   {
            end = mid - 1 ;
        }
        else    {
            start = mid + 1; 
        }
    }
    return arr[start] ;
}```

Answer 8

This question is so easy with another version of binary search:

    int solve(vector<int>& a) {
        int n = a.size();
        int k=0;
        for(int b=n/2; b>=1; b/=2)
        {
            while(k+b<n && a[k+b] >= a[0])
                k += b;
        }
        return a[k];
    }