Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumbinary-search

Find Minimum in Rotated Sorted Array

Problem (restated)

A sorted array of unique values was rotated. Find the minimum element in O(log n).

Intuition

The minimum is the only place where order “breaks.” Compare mid with the right end to decide which half is sorted.

Approaches

Binary search on rotation

Tested only

Time O(log n)Space O(1)

Idea. If nums[mid] > nums[hi], min is to the right; else min is at mid or left.

Walkthrough. [3,4,5,1,2] → mid=5 > 2 → search right → min=1.

Trade-offs. Linear min scan is simpler but fails log-time requirement.

Solution

export function findMin(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! > nums[hi]!) lo = mid + 1;
    else hi = mid;
  }
  return nums[lo]!;
}

export function findMin(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! > nums[hi]!) lo = mid + 1;
    else hi = mid;
  }
  return nums[lo]!;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?