Find Minimum in Sorted Rotated Array

mediumSave

ArrayBinary Search

Suppose an array of integers originally sorted in ascending order 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 must find and return the minimum element from the modified array. The modified array is guaranteed to contain at least one integer and no duplicates.

Example 1

Input

[
  4,
  5,
  6,
  7,
  0,
  1,
  2
]

Output

Explanation. The array was rotated at the index 3. The smallest value is the number 0.

Example 2

Input

[
  11,
  13,
  15,
  17,
  -8,
  2,
  5
]

Output

-8

Explanation. The array was rotated at the index 3. The smallest value is the number -8.

Example 3

Input

[
  2,
  3,
  4,
  5,
  6,
  7,
  8,
  1
]

Output

Explanation. The array was rotated at the index 7. The smallest value is the number 1.

Example 4

Input

[
  5
]

Output

Explanation. The array contains only one element so there is no rotation at all. The smallest element is 5.

Follow-up: How will your solution change if duplicates are allowed in the array?

Constraints:

The array will not be empty and will contain at least one integer. All elements are unique. There is no limitation on the number of elements in the array.

Views: 4