LeetCode #33: Search in Rotated Sorted Array — Solved in Java

Linear Scan Over the Array and Single Pass Binary Search

Image Source

The LeetCode problem Search in Rotated Sorted Array asks you to find the index of a target inside an array that started sorted and then shifted at some unknown pivot. Values still rise in order, but a rotation moment splits that rising sequence into two pieces. The task returns the index where the target appears or -1 if it never shows up. Even though the array no longer looks fully sorted, it still follows patterns that help narrow down where a match can hide.

Working toward a solution in Java comes down to reading those patterns and deciding how much structure you want to rely on. A simple scan works when you want to walk through the array without thinking about rotation at all. A more refined plan treats every window as partly sorted and asks which side stays in order. That view makes it possible to shrink the search with the same mid-point checks used in regular binary search. These two options give the right answer, but they approach the array in different ways and shows two distinct mindsets for solving this problem.

LeetCode: Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000

• -10^4 <= nums[i] <= 10^4

• All values of nums are unique.

• nums is an ascending array that is possibly rotated.

• -10^4 <= target <= 10^4

Solution 1: Linear Scan Over the Array

This version treats the array like any normal list of integers and just walks across it until it either finds the target or reaches the end. Rotation does not affect it, because the code never relies on sorting.