Locate Lowest Element in a Rotated Array

You're in an Adobe phone screen and the interviewer gives you an array: [4,5,6,7,0,1,2]. "This was sorted in ascending order, then rotated some number of times. Find the smallest element, and do it in O(log n)." You know this one. It's a classic binary search problem that shows up at Microsoft, Meta, Google, Amazon, and just about every major tech company. On Firecode we call it "Locate Lowest Element in a Rotated Array," but you'll find it elsewhere under the name Find Minimum in Rotated Sorted Array. The O(log n) constraint is the giveaway that binary search is involved, but the trick is figuring out which half of the array to search at each step.

TL;DR

Use binary search with two pointers, left and right. At each step, compute mid and compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum is in the right half, so set left = mid + 1. Otherwise, the minimum is at mid or to its left, so set right = mid. When left == right, you've found the minimum. This runs in O(log n) time and O(1) space.

Prefer a different language? Jump to solutions in other languages.

Understanding the Rotation

A sorted array like [0,1,2,4,5,6,7] gets rotated at some pivot, producing something like [4,5,6,7,0,1,2]. After rotation, the array splits into two sorted halves joined at the pivot point.

Original sorted array: [0, 1, 2, 4, 5, 6, 7]

After rotation: [4, 5, 6, 7, 0, 1, 2]. The highlighted boundary marks where the two sorted segments meet.

The minimum sits right at the start of the second sorted segment. In a fully sorted (unrotated) array, the minimum is simply the first element. The challenge is finding that transition point efficiently without scanning every element.

Why Binary Search Works Here

Standard binary search requires a fully sorted array. A rotated sorted array isn't fully sorted, but it has enough structure to cut the search space in half at each step. The observation is straightforward:

• Pick the middle element.
• If nums[mid] > nums[right], the rotation point is somewhere between mid+1 and right. The minimum must be in the right half.
• If nums[mid] <= nums[right], the segment from mid to right is sorted and ascending. The minimum is at mid or somewhere to its left.

Each comparison eliminates half the candidates. That's all you need for O(log n).

This decision logic runs at every iteration. The single comparison adds O(1) work per step, preserving the logarithmic bound.

Walkthrough: [3, 4, 5, 1, 2]

Rotated array: [3, 4, 5, 1, 2]. The rotation point is between indices 2 and 3.

Step 0: left=0, right=4, mid=2. nums[2]=5 and nums[4]=2. Since 5 > 2, the minimum is in the right half. Set left = mid + 1 = 3.

Step 1: left=3, right=4, mid=3. nums[3]=1 and nums[4]=2. Since 1 <= 2, the minimum is at mid or to its left. Set right = mid = 3.

Step 2: left == right == 3. nums[3] = 1. That's the answer.

Two iterations to find the minimum in a 5-element array. Binary search at work.

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

Step 0: mid=3, nums[3]=7, nums[right]=2. 7 > 2, so search right. left = 4.

Step 1: mid=5, nums[5]=1, nums[right]=2. 1 <= 2, so the minimum is at mid or left of it. right = 5.

Step 2: mid=4, nums[4]=0, nums[right]=1. 0 <= 1, so right = 4.

Step 3: left == right == 4. nums[4] = 0. Done.

Three iterations for a 7-element array. Standard binary search on 7 elements takes at most ceil(log2(7)) = 3 comparisons, so we're right in line.

Edge Case: No Rotation

When the array is fully sorted (rotated n times, which is equivalent to zero rotation), the algorithm still works.

Fully sorted: [11, 13, 15, 17]

Since every nums[mid] is less than or equal to nums[right], the algorithm keeps pulling right toward left until they meet at index 0. No special-casing required.

Implementation

public class Solution {

  public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
      int mid = left + (right - left) / 2;

      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return nums[left];
  }
}

Key implementation details:

• mid = left + (right - left) / 2 prevents integer overflow. Using (left + right) / 2 can overflow for large array indices.
• while (left < right), not while (left <= right). The loop terminates when the search range narrows to a single element. Using <= would create an infinite loop because right = mid does not shrink the range when left == right.
• right = mid, not right = mid - 1. The element at mid could be the minimum. Skipping it would miss the answer. For example, in [2, 1] with mid=0, nums[0]=2 > nums[1]=1 moves left to 1. But in [1, 2] with mid=0, nums[0]=1 <= nums[1]=2, and index 0 IS the minimum.
• left = mid + 1 is safe when nums[mid] > nums[right] because the element at mid cannot be the minimum (something smaller exists to its right).

Complexity Analysis

Time: O(log n)

Each iteration eliminates half the remaining elements. The comparison nums[mid] > nums[right] is O(1), and pointer updates are O(1). The total number of iterations is at most ceil(log2(n)).

Space: O(1)

Three integer variables: left, right, and mid. No recursion, no auxiliary data structures.

Why Compare with nums[right] Instead of nums[left]?

This is a common question in interviews. Comparing nums[mid] with nums[right] has a clean interpretation:

• nums[mid] > nums[right] means the rotation point is between mid and right, so the minimum is in the right half.
• nums[mid] <= nums[right] means mid through right is sorted, so the minimum is at mid or to its left.

Comparing with nums[left] is less reliable. When nums[left] <= nums[mid], you know the left half is sorted, but you can't immediately tell whether the minimum is the leftmost element or somewhere in the right half. The unrotated case ([1,2,3,4]) makes this ambiguous because nums[left] <= nums[mid] is always true, yet the minimum is at left, not in the right half.

Common Mistakes

• Using right = mid - 1 instead of right = mid. This skips the element at mid, which could be the minimum. It's the single most common bug in this problem.

• Using while (left <= right) instead of while (left < right). With right = mid, the condition left <= right never becomes false when left == right, creating an infinite loop.

• Comparing with nums[left] instead of nums[right]. As discussed above, this introduces edge case handling for the unrotated array that comparing with nums[right] avoids entirely.

• Returning nums[right] instead of nums[left]. When the loop ends, left == right, so either works. But conventionally, nums[left] is the expected return value, and using right can confuse readers since right was the comparison target during the loop.

Interview Tips

• Start with the observation. "A rotated sorted array has two sorted halves. Comparing the middle with the rightmost element tells me which half contains the minimum." This shows you understand the structure before writing code.

• Explain why right = mid and not mid - 1. Interviewers specifically watch for this. It's a detail that distinguishes candidates who understand the invariant from those who memorized a template.

• Trace through a small example. [3,4,5,1,2] is ideal. Five elements, two iterations, easy to draw on a whiteboard.

• Mention the duplicate variant. If the interviewer asks a follow-up, explain that duplicates break the nums[mid] > nums[right] comparison when they're equal. The fix is to decrement right by 1, but this makes the worst case O(n).

• Connect to related problems. "This is a simpler version of Search in Rotated Sorted Array, which uses the same binary search framework but searches for a specific target instead of the minimum."

Key Takeaways

• The rotation splits the array into two sorted halves. Comparing nums[mid] with nums[right] determines which half holds the minimum.
• Use right = mid (not mid - 1) because mid itself might be the minimum. Use left = mid + 1 because when nums[mid] > nums[right], the element at mid cannot be the answer.
• The loop condition is while (left < right), not while (left <= right). The algorithm converges when the pointers meet.
• The unrotated case works without special handling. When the array is fully sorted, nums[mid] <= nums[right] is always true, and the algorithm naturally converges on index 0.
• This problem is a simpler variant of Search in Rotated Sorted Array. The binary search framework is identical, but the decision logic is easier because you're always searching for the smallest element rather than a specific target.

Related Problems

Once you're comfortable with this binary search variant, try these:

• Search in Rotated Sorted Array - Same rotated array structure, but you search for a specific target value instead of the minimum
• Find Pair Indices in Sorted Array (Two Sum II) - Binary search and two pointers on a sorted array
• Combining Overlapping Ranges (Merge Intervals) - Another array problem where sorting reveals hidden structure

These are all available on Firecode, where over 50,000 engineers have practiced for technical interviews at companies like Adobe, Microsoft, Meta, and Google. Binary search on rotated arrays is one of those patterns that keeps appearing in different forms, and once you internalize the comparison-with-right technique, variants like this one become second nature.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def find_min(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]

JavaScript

class Solution {
  findMin(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return nums[left];
  }
}

TypeScript

class Solution {
  findMin(nums: number[]): number {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return nums[left];
  }
}

C++

#include <vector>

class Solution {
public:
  int findMin(std::vector<int> &nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return nums[left];
  }
};

Go

func (s *Solution) FindMin(nums []int) int {
    left, right := 0, len(nums)-1

    for left < right {
        mid := left + (right-left)/2

        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return nums[left]
}

Scala

class Solution {
  def findMin(nums: Array[Int]): Int = {
    var left = 0
    var right = nums.length - 1

    while (left < right) {
      val mid = left + (right - left) / 2
      if (nums(mid) > nums(right)) {
        left = mid + 1
      } else {
        right = mid
      }
    }

    nums(left)
  }
}

Kotlin

class Solution {
  fun findMin(nums: IntArray): Int {
    var left = 0
    var right = nums.size - 1

    while (left < right) {
      val mid = left + (right - left) / 2

      if (nums[mid] > nums[right]) {
        left = mid + 1
      } else {
        right = mid
      }
    }

    return nums[left]
  }
}

Swift

class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var left = 0
        var right = nums.count - 1

        while left < right {
            let mid = left + (right - left) / 2

            if nums[mid] > nums[right] {
                left = mid + 1
            } else {
                right = mid
            }
        }

        return nums[left]
    }
}

Rust

impl Solution {
    pub fn find_min(&self, nums: Vec<i32>) -> i32 {
        let mut left = 0;
        let mut right = nums.len() - 1;

        while left < right {
            let mid = left + (right - left) / 2;

            if nums[mid] > nums[right] {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        nums[left]
    }
}

Ruby

class Solution
  def find_min(nums)
    left = 0
    right = nums.length - 1

    while left < right
      mid = left + (right - left) / 2

      if nums[mid] > nums[right]
        left = mid + 1
      else
        right = mid
      end
    end

    nums[left]
  end
end

Dart

class Solution {
  int findMin(List<int> nums) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
      int mid = left + (right - left) ~/ 2;

      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return nums[left];
  }
}

PHP

class Solution {
    public function findMin(array $nums): int {
        $left = 0;
        $right = count($nums) - 1;

        while ($left < $right) {
            $mid = $left + intdiv($right - $left, 2);

            if ($nums[$mid] > $nums[$right]) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }

        return $nums[$left];
    }
}

C#

public class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.Length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}