Firecode logo
Sign In Start Free Trial

Pivoted Array Target Search: Binary search in a rotated sorted array

AS
Ackshaey Singh
Difficulty Hard
Time Complexity
O(log n)
Space Complexity
O(1)
Array Binary search
Adobe Meta Apple Google Amazon LinkedIn Yahoo Bloomberg Oracle

You're in an Amazon onsite and the interviewer draws an array on the whiteboard: [4,5,6,7,0,1,2]. "This was sorted, then rotated at some unknown point. Find the index of a given target in O(log n) time." You recognize this immediately. This is a rotated sorted array search problem, also known as Search in Rotated Sorted Array on other platforms like LeetCode. It appears frequently at Adobe, Meta, Apple, Google, and Amazon, and it tests whether you can adapt binary search when the sorted order is disrupted by a rotation.

TL;DR

Use a modified binary search. At each step, determine which half of the array is sorted by comparing nums[left] with nums[mid]. If the target falls within the sorted half's range, search there. Otherwise, search the other half. Each iteration still eliminates half the elements, giving 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]. The key observation: the rotated array consists of two sorted subarrays joined at the pivot point.

Loading visualization...

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

Loading visualization...

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

The pivot is where the order breaks. Elements before it form one sorted segment, elements after form another. Standard binary search fails because the midpoint comparison can't reliably tell you which direction to go. But with one extra check per iteration, you can recover the O(log n) guarantee.

The Core Insight

In any subarray of a rotated sorted array, at least one half is always sorted. When you compute mid, either the left half [left..mid] or the right half [mid..right] is in ascending order. You can determine which by a single comparison:

  • If nums[left] <= nums[mid], the left half is sorted.
  • Otherwise, the right half is sorted.

Once you know which half is sorted, checking whether the target falls within that half's range is a straightforward bounds check. If it does, search there. If not, search the other half.

Loading visualization...

This decision tree runs at every iteration. The sorted-half identification adds O(1) work per step, so the overall complexity stays O(log n).

Walkthrough: Target = 2

For [4,5,6,7,0,1,2] with target 2:

Loading visualization...

Step 0: mid=3, nums[3]=7. Left half [4,5,6,7] is sorted (4 <= 7). Target 2 is not in [4, 7), so we search right.

Step 1: mid=5, nums[5]=1. Right half [1,2] is sorted (1 <= 2). Target 2 is not in (1, 2]... wait, actually 2 <= 2 is true, but 1 < 2 is also true, so 2 IS in (1, 2]. The target is at the boundary. We search right: left = 6.

Step 2: mid=6, nums[6]=2. Match! Return index 6.

Walkthrough: Target = 0

Loading visualization...

Step 0: Left half [4,5,6,7] is sorted. Target 0 is not in [4, 7), so search right.

Step 1: Right half [1,2] is sorted. Target 0 is not in (1, 2], so search left: right = 4.

Step 2: left=4, right=4, mid=4. nums[4] = 0. Match! Return index 4.

Walkthrough: Target = 3 (Not Found)

Loading visualization...

The search narrows to a single element that doesn't match, then left crosses right. Return -1.

Implementation

public class Solution {

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

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

      if (nums[mid] == target) {
        return mid;
      }

      if (nums[left] <= nums[mid]) {
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[right]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }

    return -1;
  }
}

Key implementation details:

  • mid = left + (right - left) / 2 avoids integer overflow compared to (left + right) / 2.
  • nums[left] <= nums[mid] uses <= (not <) to handle the case where left == mid, which occurs when only two elements remain.
  • The boundary checks are asymmetric on purpose: nums[left] <= target && target < nums[mid] for the left half, and nums[mid] < target && target <= nums[right] for the right half. This ensures the target is strictly within the sorted half's range (excluding mid itself, which was already checked).

Walkthrough with a Larger Example

For [2,3,4,5,6,7,0,1] with target 1:

Loading visualization...

Four steps to find target 1 at index 7 in an 8-element array. Standard binary search on 8 elements takes at most log2(8) = 3 comparisons, so the rotated version adds at most one extra step due to the pivot crossing.

Complexity Analysis

Time: O(log n)

Each iteration eliminates half the remaining elements, identical to standard binary search. The extra comparison to determine which half is sorted is O(1), so it doesn't affect the logarithmic bound.

Space: O(1)

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

Why Not Find the Pivot First?

A two-pass approach finds the pivot (rotation point) first with one binary search, then runs standard binary search on the correct half. This also runs in O(log n) time, but it requires two passes and more complex pivot-finding logic. The single-pass approach is cleaner, handles edge cases more naturally, and is what interviewers expect.

Edge Cases

  1. No rotation. The array is fully sorted. nums[left] <= nums[mid] is always true, and the algorithm reduces to standard binary search.

  2. Single element. left == right == mid. Either it matches the target or it doesn't. The loop runs once.

  3. Target at the pivot boundary. For [4,5,6,7,0,1,2] with target 7 (last element of the first segment), the algorithm correctly identifies the left half as sorted and finds 7 within [4, 7].

  4. Two elements. [3, 1] with target 1. mid = 0, nums[0] = 3 != 1. Left half [3] is sorted. Target 1 is not in [3, 3), so search right. left = 1, right = 1, mid = 1. Found.

Common Mistakes

  • Using < instead of <= in nums[left] <= nums[mid]. When left == mid (two-element subarray), < incorrectly identifies the left half as unsorted. This causes the algorithm to search the wrong half.

  • Getting the target range checks wrong. The left-half check is nums[left] <= target && target < nums[mid]. The right-half check is nums[mid] < target && target <= nums[right]. Mixing up the strict and non-strict inequalities is the most common source of bugs.

  • Integer overflow in midpoint calculation. Always use left + (right - left) / 2 instead of (left + right) / 2. For arrays with up to 500 elements this doesn't matter in practice, but it's good habit and interviewers notice.

Interview Tips

  • Clarify constraints. "Are all elements unique? Can the array be unrotated?" Both matter for correctness. This problem guarantees unique elements; with duplicates, the worst case degrades to O(n).

  • Start with the observation. "In a rotated sorted array, at least one half around any midpoint is always sorted." This single sentence shows you understand the core idea.

  • Draw the array. Sketch [4,5,6,7,0,1,2] on the whiteboard and mark left, mid, right. Walk through one or two iterations showing how the pointers move.

  • Compare with standard binary search. "This is binary search with one extra check per iteration to determine which half is sorted. The time complexity stays O(log n)."

  • Mention the duplicate variant. If the interviewer asks a follow-up, explain that duplicates (e.g., [2,5,6,0,0,1,2]) break the nums[left] <= nums[mid] check because equal values don't tell you which side the pivot is on. The fix is to skip duplicates by incrementing left, but this makes the worst case O(n).

Related Problems

Once you're comfortable with modified binary search on rotated arrays, try these:

  • Find Minimum in Rotated Sorted Array - Same structure, but you search for the pivot point itself instead of a specific target
  • Find Pair Indices in Sorted Array (Two Sum II) - Binary search / two pointers on a sorted array
  • Subarray with Maximum Total (Maximum Subarray) - Another array problem that rewards recognizing structure
  • Leap to the Finish Line (Jump Game) - Array traversal with a different decision pattern

These are all available on Firecode, where over 50,000 engineers have practiced for technical interviews at companies like Adobe, Meta, Google, and Amazon. Binary search is one of the most versatile patterns in coding interviews, and rotated array search is the problem that separates candidates who memorize templates from those who truly understand the technique.

Solutions in Other Languages

Python

from typing import List

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

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

            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

JavaScript

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

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

      if (nums[mid] === target) {
        return mid;
      }

      if (nums[left] <= nums[mid]) {
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[right]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }

    return -1;
  }
}

TypeScript

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

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

      if (nums[mid] === target) {
        return mid;
      }

      if (nums[left] <= nums[mid]) {
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[right]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }

    return -1;
  }
}

C++

#include <vector>

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

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

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
};

Go

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

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

        if nums[mid] == target {
            return mid
        }

        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
}

Scala

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

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

      if (nums(mid) == target) {
        return mid
      }

      if (nums(left) <= nums(mid)) {
        if (nums(left) <= target && target < nums(mid)) {
          right = mid - 1
        } else {
          left = mid + 1
        }
      } else {
        if (nums(mid) < target && target <= nums(right)) {
          left = mid + 1
        } else {
          right = mid - 1
        }
      }
    }

    -1
  }
}

Kotlin

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

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

      if (nums[mid] == target) {
        return mid
      }

      if (nums[left] <= nums[mid]) {
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1
        } else {
          left = mid + 1
        }
      } else {
        if (nums[mid] < target && target <= nums[right]) {
          left = mid + 1
        } else {
          right = mid - 1
        }
      }
    }

    return -1
  }
}

Swift

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

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

            if nums[mid] == target {
                return mid
            }

            if nums[left] <= nums[mid] {
                if nums[left] <= target && target < nums[mid] {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            } else {
                if nums[mid] < target && target <= nums[right] {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            }
        }

        return -1
    }
}

Rust

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

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

            if nums[mid as usize] == target {
                return mid;
            }

            if nums[left as usize] <= nums[mid as usize] {
                if nums[left as usize] <= target && target < nums[mid as usize] {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if nums[mid as usize] < target && target <= nums[right as usize] {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        -1
    }
}

C#

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

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

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

Dart

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

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

      if (nums[mid] == target) {
        return mid;
      }

      if (nums[left] <= nums[mid]) {
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[right]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }

    return -1;
  }
}

PHP

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

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

            if ($nums[$mid] === $target) {
                return $mid;
            }

            if ($nums[$left] <= $nums[$mid]) {
                if ($nums[$left] <= $target && $target < $nums[$mid]) {
                    $right = $mid - 1;
                } else {
                    $left = $mid + 1;
                }
            } else {
                if ($nums[$mid] < $target && $target <= $nums[$right]) {
                    $left = $mid + 1;
                } else {
                    $right = $mid - 1;
                }
            }
        }

        return -1;
    }
}

Ruby

class Solution
  def search(nums, target)
    left = 0
    right = nums.length - 1

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

      if nums[mid] == target
        return mid
      end

      if nums[left] <= nums[mid]
        if nums[left] <= target && target < nums[mid]
          right = mid - 1
        else
          left = mid + 1
        end
      else
        if nums[mid] < target && target <= nums[right]
          left = mid + 1
        else
          right = mid - 1
        end
      end
    end

    -1
  end
end

Frequently Asked Questions

What is a rotated sorted array?
A rotated sorted array is a sorted array that has been shifted at some unknown pivot point. For example, [0,1,2,4,5,6,7] rotated at index 3 becomes [4,5,6,7,0,1,2]. The array consists of two sorted subarrays separated by the rotation point, where the largest element is followed by the smallest.
Why can you use binary search on a rotated sorted array?
Even though the array is not fully sorted, at any midpoint at least one half of the array is guaranteed to be sorted. You can determine which half is sorted by comparing the leftmost element with the middle element. Once you identify the sorted half, you can check whether the target falls within that range and eliminate half the search space each iteration.
How do you determine which half of a rotated sorted array is sorted?
Compare nums[left] with nums[mid]. If nums[left] ≤ nums[mid], the left half from left to mid is sorted in ascending order. Otherwise, the right half from mid to right is sorted. This comparison works because the rotation point can only be in the unsorted half.
What is the time complexity of searching in a rotated sorted array?
O(log n). Each iteration of the modified binary search eliminates half the remaining elements, just like standard binary search. The rotation does not change the number of comparisons needed, only the logic for deciding which half to search.
What is the space complexity of searching in a rotated sorted array?
O(1). The algorithm uses only a constant number of variables (left, right, mid) regardless of input size. No additional data structures, recursion stacks, or auxiliary arrays are needed.
What happens if the array is not rotated at all?
The algorithm handles unrotated arrays correctly. If the array is fully sorted (rotation at index 0), nums[left] ≤ nums[mid] is always true, and the algorithm behaves identically to standard binary search. No special-casing is needed.
Can you solve this problem with a linear scan instead of binary search?
Yes, a linear scan in O(n) time works. However, interviewers expect the O(log n) binary search solution because the problem specifically asks you to exploit the sorted structure. A linear scan ignores the key constraint and will not pass most interview evaluations.
What are the common mistakes when implementing search in a rotated sorted array?
The most common mistakes are: using strict less-than instead of less-than-or-equal when checking if the left half is sorted (fails when left equals mid), getting the boundary conditions wrong when checking if the target is in the sorted half, and integer overflow when computing the midpoint (use left + (right - left) / 2 instead of (left + right) / 2).
How does this problem relate to finding the minimum in a rotated sorted array?
Finding the minimum is a simpler version of the same pattern. Instead of searching for a specific target, you search for the rotation point where the array transitions from the larger segment to the smaller segment. The same binary search framework applies, with the decision logic adjusted to always move toward the smaller half.
What are follow-up problems after mastering search in a rotated sorted array?
Natural follow-ups include Search in Rotated Sorted Array II (with duplicates, which degrades worst-case to O(n)), Find Minimum in Rotated Sorted Array, and Find Minimum in Rotated Sorted Array II. These all build on the same modified binary search framework and are commonly asked together in interview rounds at Google, Meta, and Amazon.