CA 20 - Search in Rotated Sorted Array

1.Problem Understanding

Given a sorted array to be rotated.

Example:
[4, 5, 6, 7, 0, 1, 2]
Originally:
[0, 1, 2, 4, 5, 6, 7]

2.Key Insight
At any point, one half is always sorted
Even in rotated array.

3.Approach (Core Logic)
At every step:
Find mid
Check which half is sorted:
Left sorted → nums[left] <= nums[mid]
Right sorted → otherwise

4.Decision Making (This is the real algorithm)
Case 1: Left half is sorted
nums[left] <= nums[mid]

If target lies in this range → search left
Else → search right
Case 2: Right half is sorted

5.Example

Array:

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

Step 1:

mid = 7
Left sorted → [4,5,6,7]

Target not here → go right

Step 2:

Now search [0,1,2]
Found target

6.Algorithm Steps
Initialize left = 0, right = n-1
While left ≤ right:
Find mid
If target found → return
Check sorted half
Decide direction
Return -1 if not found