Search in Rotated Sorted Array | Modified Binary Search

Problem Statement

Given a rotated sorted array nums and an integer target, return the index of target.

If the target does not exist, return -1.

You must solve it in:

O(log N)

Enter fullscreen mode Exit fullscreen mode

time.

Brute Force Intuition

In an interview, you can explain it like this:

We can scan the array from left to right and compare every element with the target. As soon as we find the target, we return its index. This works but does not utilize the sorted nature of the array.

Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int search(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] == target)
                return i;
        }

        return -1;
    }
}

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

A normal Binary Search works only when the array is completely sorted.

But after rotation:

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

Enter fullscreen mode Exit fullscreen mode

the entire array is not sorted.

However, one important property still remains:

At least one half is always sorted.

This observation allows us to eliminate half of the search space every time.

Pattern Recognition

Whenever you see:

• Sorted Array
• Rotation
• Search Target

Think:

Modified Binary Search

Key Observation

For any mid:

[4,5,6 | 7 | 0,1,2]

Enter fullscreen mode Exit fullscreen mode

One side will always be sorted.

Either:

Left Half Sorted

Enter fullscreen mode Exit fullscreen mode

or

Right Half Sorted

Enter fullscreen mode Exit fullscreen mode

Once we identify the sorted half, we check whether the target lies inside it.

Optimal Approach

Case 1

Left Half Sorted

if(nums[low] <= nums[mid])

Enter fullscreen mode Exit fullscreen mode

Example:

4 5 6 7

Enter fullscreen mode Exit fullscreen mode

If target lies within:

nums[low] <= target < nums[mid]

Enter fullscreen mode Exit fullscreen mode

Search left.

Otherwise search right.

Case 2

Right Half Sorted

else

Enter fullscreen mode Exit fullscreen mode

Example:

0 1 2

Enter fullscreen mode Exit fullscreen mode

If target lies within:

nums[mid] < target <= nums[high]

Enter fullscreen mode Exit fullscreen mode

Search right.

Otherwise search left.

Optimal Java Solution

class Solution {

    public int search(int[] arr, int target) {

        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {

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

            if (arr[mid] == target)
                return mid;

            if (arr[low] <= arr[mid]) {

                if (arr[low] <= target &&
                    target < arr[mid]) {

                    high = mid - 1;

                } else {

                    low = mid + 1;
                }

            } else {

                if (arr[mid] < target &&
                    target <= arr[high]) {

                    low = mid + 1;

                } else {

                    high = mid - 1;
                }
            }
        }

        return -1;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

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

Enter fullscreen mode Exit fullscreen mode

Iteration 1

low = 0
high = 6

mid = 3
nums[mid] = 7

Enter fullscreen mode Exit fullscreen mode

Left side:

4 5 6 7

Enter fullscreen mode Exit fullscreen mode

is sorted.

Check:

0 lies between 4 and 7 ?

Enter fullscreen mode Exit fullscreen mode

No.

Move Right.

low = 4

Enter fullscreen mode Exit fullscreen mode

Iteration 2

low = 4
high = 6

mid = 5
nums[mid] = 1

Enter fullscreen mode Exit fullscreen mode

Left side:

0 1

Enter fullscreen mode Exit fullscreen mode

is sorted.

Check:

0 lies between 0 and 1 ?

Enter fullscreen mode Exit fullscreen mode

Yes.

Move Left.

high = 4

Enter fullscreen mode Exit fullscreen mode

Iteration 3

low = 4
high = 4

mid = 4
nums[mid] = 0

Enter fullscreen mode Exit fullscreen mode

Found Target ✅

Answer = 4

Enter fullscreen mode Exit fullscreen mode

Why This Works?

Even though the array is rotated:

One half always remains sorted.

Enter fullscreen mode Exit fullscreen mode

Using that sorted half, we can determine whether the target can exist there.

This allows us to eliminate half the search space every iteration.

Complexity Analysis

Metric Complexity Time Complexity O(log N) Space Complexity O(1)

Interview One-Liner

In a rotated sorted array, at least one half is always sorted. Identify the sorted half and decide whether the target lies inside it to eliminate half the search space.

Pattern Learned

Sorted Array
+
Rotation
+
Search

=> Modified Binary Search

Enter fullscreen mode Exit fullscreen mode

Similar Problems

• Search in Rotated Sorted Array
• Search in Rotated Sorted Array II
• Find Minimum in Rotated Sorted Array
• Single Element in Sorted Array
• Peak Element

Memory Trick

Think:

Find Sorted Half
        ↓
Target Inside ?
        ↓
Yes → Go There
No  → Go Other Half

Enter fullscreen mode Exit fullscreen mode

Mental Model

Normal Binary Search
→ Array Fully Sorted

Rotated Binary Search
→ One Half Sorted

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Search in Rotated Sorted Array”

your brain should immediately think:

Find Sorted Half → Check Target Range → Eliminate Half