Show problems as
Classic problem #153MediumArrayBinary Search

Find Minimum in Rotated Sorted Array

Real-world version: Wrapped Buoy Low Offset
Tracked in this browser only
Read Find Minimum in Rotated Sorted Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstBasic Binary Search · Binary Search, animated step by step

A weather buoy stores calibration offsets in a ring buffer. The offsets were written into the ring in strictly increasing order, one per slot, and afterwards the buffer's start marker was slid forward by some number of slots. Dumping the ring from the marker therefore hands you the increasing run cut at one slot, with the piece before the cut moved behind the piece after it. The marker may also have been slid all the way around the ring, and then the dump comes out plainly increasing.

Offsets can be below freezing, so negative values are ordinary. No two offsets are equal.

Given the dump offsets, report the smallest offset it holds. Your routine must settle the answer in logarithmic time, so reading every slot is off the table.

Examples

Example 1

Input
offsets = [-4, -1, 3, -9, -7]
Output
-9

The increasing run was -9, -7, -4, -1, 3; the cut fell after -1, so the run restarts at slot 3 and the low offset sits there.

Example 2

Input
offsets = [2, 7, 9]
Output
2

The marker travelled the full ring, so the dump is still increasing and the low offset is the first slot.

Example 3

Input
offsets = [5000, -5000]
Output
-5000

Two slots with the cut between them, so the second slot restarts the run.

Constraints

  • n == offsets.length
  • 1 <= n <= 5000
  • -5000 <= offsets[i] <= 5000
  • No two offsets are equal
  • offsets is a strictly increasing run whose start marker was slid forward between 1 and n slots

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def lowest_offset(offsets: list[int]) -> int:
Java
public int lowestOffset(int[] offsets)

More on the same topics