DEV Community

Wenqi Jiang
Wenqi Jiang

Posted on

[Binary Search]Find the Largest Number in a Rotated List

#algorithms #java #100daysofcode #programming

Description

You are given a list of unique integers nums that is sorted in ascending order and is rotated at some pivot point. Find the maximum number in the rotated list.

Can you solve it in O(log*n*)?

Constraints:

  • n ≤ 100,000 where n is the length of nums.

Example 1

Input 

arr = [6, 7, 8, 1, 4]
Enter fullscreen mode Exit fullscreen mode

Output 

arr = [6, 7, 8, 1, 4]
Enter fullscreen mode Exit fullscreen mode

Explanation 

The original sorted array of [1, 4, 6, 7, 8] was rotated at index 2 and results in the input array [6, 7, 8, 1, 4,]. And the largest number is 8.
Enter fullscreen mode Exit fullscreen mode

Example 2

Input 

arr = [1, 2, 3]
Enter fullscreen mode Exit fullscreen mode

Output 

3
Enter fullscreen mode Exit fullscreen mode

Example 3

Input 

arr = [1]
Enter fullscreen mode Exit fullscreen mode

Output 

1
Enter fullscreen mode Exit fullscreen mode

Example 4

Input 

arr = [10, 1, 2, 3, 4, 7]
Enter fullscreen mode Exit fullscreen mode

Output 

10
Enter fullscreen mode Exit fullscreen mode

Intuition

  1. Binary Search
  2. if (arr[mid+1] < arr[mid]), mid is the largest value index

Implementation 

import java.util.*;

class Solution {
    // Time=O(logn), space=O(1)
    public int solve(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 0....mid, mid+1....right
            if (mid + 1 < arr.length && arr[mid + 1] < arr[mid]) {
                return arr[mid];
            }
            if (arr[left] <= arr[mid]) {
                // left side sorted
                // 8,9,10,4,5,6
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return arr[left];
    }
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity

  • Time: O(logn)
  • Space: O(1)

Top comments (0)