Mohith

Posted on Mar 20

Search in Rotated Sorted Array – CA20

My Thinking and Approach

Introduction

In this problem, I was given a sorted array that has been rotated at some unknown index, and I needed to find the index of a target element.

At first, it looked like a normal binary search problem, but the rotation made it tricky. I had to rethink how binary search works in this situation.

Problem Statement

Given a rotated sorted array with distinct elements
Find the index of a target value
If the target is not present, return -1
Required time complexity: O(log n)

My Initial Thought

Initially, I thought:

Just apply normal binary search

But that does not work because the array is not fully sorted anymore due to rotation.

Then I thought:

Find pivot (rotation point)
Then apply binary search

This works, but it adds extra steps.

So I looked for a more optimized single-pass approach.

Key Observation

Even though the array is rotated:

At least one half (left or right) will always be sorted

This observation is the key to solving the problem efficiently.

Optimized Approach (Modified Binary Search)

Instead of finding the pivot separately, I used a modified binary search.

Idea

At every step:
- Check which half is sorted
- Decide where the target lies
- Narrow down the search space

My Approach

Initialize:

low = 0
high = n - 1

Loop while low <= high:

Find mid:
mid = low + (high - low) / 2
If nums[mid] == target → return mid
Check if left half is sorted:
- If nums[low] <= nums[mid]:
  - If target lies in this range: → move left (high = mid - 1)
  - Else: → move right (low = mid + 1)
Else (right half is sorted):
- If target lies in right range: → move right (low = mid + 1)
- Else: → move left (high = mid - 1)

Code (Java)

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

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

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

        return -1;
    }
}

Example Walkthrough

Example 1

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

Steps:

mid = 3 → value = 7
Left half is sorted → target not in range → go right
mid = 5 → value = 1
Right half sorted → target not in range → go left
mid = 4 → value = 0 → found

Output:
4

Example 2

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

Output:
-1

Example 3

Input:
nums = [1], target = 0