Search in Rotated Sorted Array in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a rotated sorted array?

A rotated sorted array is an array that was originally sorted but then rotated (shifted) at some pivot point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7].

beginner

Why can't we use simple binary search directly on a rotated sorted array?

Because the array is not fully sorted in ascending order due to rotation, simple binary search may fail. We need to identify which part of the array is sorted to decide where to search next.

intermediate

In the search algorithm, how do we decide which half to search next?

We check if the left half is sorted by comparing the start and middle elements. If sorted, we check if the target lies in this range. If yes, search left half; else, search right half. If left half is not sorted, right half must be sorted, so we do the same check there.

beginner

What is the time complexity of searching in a rotated sorted array using the modified binary search?

The time complexity is O(log n) because each step halves the search space, similar to normal binary search.

intermediate

Show the key steps of the binary search in rotated sorted array with an example array [6,7,0,1,2,4,5] searching for 2.

1. Start with low=0, high=6, mid=3 (value=1).<br>2. Left half [6,7,0,1] is not sorted, right half [1,2,4,5] is sorted.<br>3. Target 2 lies in right half range (1 to 5), so search right half.<br>4. Update low=4, high=6, mid=5 (value=4).<br>5. Left half [2,4] is sorted, target 2 lies in this range.<br>6. Update high=4, mid=4 (value=2), found target at index 4.

What is the main challenge when searching in a rotated sorted array?

A The array contains duplicates

B The array is not fully sorted in ascending order

C The array is too large

D The array is sorted in descending order

The rotation breaks the full ascending order, so normal binary search needs adjustment.

If the left half of the array is sorted, what should you check next?

A If the right half is sorted

B If the target is greater than the end element

C If the target is less than the start element

D If the target lies between the start and mid elements

If left half is sorted, check if target lies in that range to decide where to search.

What is the time complexity of the search in a rotated sorted array using binary search?

A O(log n)

B O(n)

C O(n log n)

D O(1)

The search halves the search space each time, so it is O(log n).

In the array [4,5,6,7,0,1,2], what is the pivot point where rotation happened?

A Between 7 and 0

B Between 2 and 4

C Between 5 and 6

D Between 1 and 2

Rotation happened between the largest element 7 and smallest element 0.

If the left half is not sorted, what can we conclude about the right half?

A Right half is empty

B Right half is also not sorted

C Right half must be sorted

D Right half contains duplicates

If left half is not sorted, the right half must be sorted in a rotated sorted array.

Explain how to search for a target in a rotated sorted array using binary search.

Think about how rotation affects sorting and how to use that to guide search.

Describe the difference between normal binary search and binary search in a rotated sorted array.

Focus on how rotation changes the array order.