Search in Rotated Sorted Array in DSA Javascript - Execution Trace

Concept Flow - Search in Rotated Sorted Array

Start with low=0, high=n-1

↓

Calculate mid = (low+high)//2

↓

Check if nums[mid

↓

Return mid

↓

Left half sorted

↓

Check if target in left

↓

Adjust high or low

↓

Repeat until low > high

↓

Return -1 if not found

The search uses a modified binary search to find the target in a rotated sorted array by checking which half is sorted and narrowing the search range accordingly.

Execution Sample

DSA Javascript

function search(nums, target) {
  let low = 0, high = nums.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 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;
}

This code searches for a target value in a rotated sorted array using a modified binary search.

Execution Table

Step	Operation	low	high	mid	nums[mid]	Check Sorted Half	Adjust low/high	Search Range	Result
1	Initialize low and high	0	6	-	-	-	-	[0..6]	-
2	Calculate mid	0	6	3	7	Left half sorted (nums[0]=4 <= nums[3]=7)	Target=3 not in [4..7), set low=mid+1=4	[4..6]	-
3	Calculate mid	4	6	5	1	Left half sorted (nums[4]=0 <= nums[5]=1)	Target=3 not in [0..1), set low=mid+1=6	[6..6]	-
4	Calculate mid	6	6	6	3	Single element, check nums[mid]	nums[mid] == target, return 6	[6..6]	6
5	Exit	-	-	-	-	-	-	-	Target found at index 6

💡 Search ends when target is found or low > high (not found). Here target found at index 6.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
low	0	4	6	6	6
high	6	6	6	6	6
mid	-	3	5	6	6
nums[mid]	-	7	1	3	3

Key Moments - 3 Insights

Why do we check if nums[low] <= nums[mid] to decide which half is sorted?

Because in a rotated sorted array, one half is always sorted. Checking nums[low] <= nums[mid] tells us if the left half is sorted, helping us decide where to search next (see execution_table step 2).

Why do we adjust low or high based on target's position relative to nums[low], nums[mid], and nums[high]?

We narrow the search to the half where the target can be. If target lies within the sorted half's range, we search there by adjusting low or high accordingly (see execution_table steps 2 and 3).

What happens if the target is not in the array?

The loop continues adjusting low and high until low > high, then returns -1 indicating target not found (not shown in this example but explained in exit_note).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of 'low' after adjustment?

A 4

B 6

C 5

D 3

💡 Hint

Check the 'Adjust low/high' and 'low' columns in execution_table row for step 3.

At which step does the condition low <= high become false if the target is not found?

A After step 4

B Before step 1

C When low > high during the loop

D At step 2

💡 Hint

Refer to the exit_note and loop condition in the code description.

If the target was 5 instead of 3, how would the search range change at step 2?

A high would be set to mid - 1 = 2

B low would be set to mid + 1 = 4

C low would remain 0

D high would be set to mid + 1 = 4

💡 Hint

Check the 'Adjust low/high' logic in step 2 for target 3 and think about target 5.

Concept Snapshot

Search in Rotated Sorted Array:
- Use binary search with low, high pointers
- Calculate mid = (low + high) // 2
- Check if nums[mid] == target
- Determine which half is sorted by comparing nums[low] and nums[mid]
- Narrow search to half containing target
- Repeat until found or low > high
- Return index or -1 if not found

Full Transcript

This concept shows how to search for a target value in a rotated sorted array using a modified binary search. We start with low and high pointers at the ends of the array. We calculate mid and check if nums[mid] equals the target. If not, we check which half of the array is sorted by comparing nums[low] and nums[mid]. Depending on which half is sorted and where the target lies, we adjust low or high to narrow the search range. We repeat this until we find the target or low becomes greater than high, meaning the target is not in the array. The execution table traces these steps with variable values and decisions. The variable tracker shows how low, high, mid, and nums[mid] change. Key moments clarify why we check sorted halves and how we adjust pointers. The visual quiz tests understanding of these steps. This method efficiently finds the target in O(log n) time even if the array is rotated.