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.

Practice

1. What is the main challenge when searching in a rotated sorted array compared to a normal sorted array?

easy

A. The array contains only negative numbers

B. The array elements are all the same

C. The array is sorted in descending order

D. The array is split into two sorted parts, so normal binary search needs adjustment

Solution

1. Step 1: Understand the array structure

   A rotated sorted array is created by taking a sorted array and rotating it at some pivot, splitting it into two sorted parts.

2. Step 2: Reason about search difficulty

   Normal binary search assumes the whole array is sorted, but here the array is split, so we must adjust the search to handle two sorted parts.

3. Final Answer:

   The array is split into two sorted parts, so normal binary search needs adjustment -> Option D

4. Quick Check:

   Rotated array = split sorted parts [OK]

Hint: Look for the pivot splitting the array into two sorted halves [OK]

Common Mistakes:

• Assuming the entire array is sorted
• Ignoring the pivot point
• Using linear search instead of binary search

2. Which of the following is the correct syntax to start a binary search in a rotated sorted array in JavaScript?

easy

A. let left = 0, right = arr.length - 1;

B. let left = 1, right = arr.length;

C. let left = -1, right = arr.length;

D. let left = 0, right = arr.length;

Solution

1. Step 1: Identify valid index range for binary search

   Binary search uses zero-based indexing, so left starts at 0 and right at last index (length - 1).

2. Step 2: Check each option

   let left = 0, right = arr.length - 1; correctly sets left=0 and right=arr.length-1. Others have invalid ranges or off-by-one errors.

3. Final Answer:

   let left = 0, right = arr.length - 1; -> Option A

4. Quick Check:

   Index range = 0 to length-1 [OK]

Hint: Start binary search with left=0 and right=length-1 [OK]

Common Mistakes:

• Using right = arr.length (out of bounds)
• Starting left at 1 instead of 0
• Negative indices for left or right

3. What will be the output of the following code snippet?

const arr = [4,5,6,7,0,1,2];
function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}
console.log(search(arr, 0));

medium

A. 6

B. 0

C. 4

D. -1

Solution

1. Step 1: Understand the array and target

   The array is rotated sorted: [4,5,6,7,0,1,2], target is 0.

2. Step 2: Trace the binary search steps

   Initial left=0, right=6, mid=3 (value 7). Left half is sorted (4 to 7). Target 0 is not in left half, so search right half: left=4, right=6.
   New mid=5 (value 1). Left half (0 to 1) is sorted. Target 0 is in left half, so right=4.
   New mid=4 (value 0), found target at index 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Target 0 found at index 4 [OK]

Hint: Check which half is sorted, then decide search side [OK]

Common Mistakes:

• Not updating left/right correctly
• Confusing sorted half
• Returning wrong index or -1

4. Identify the bug in this search function for rotated sorted array:

function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

medium

A. The loop condition should be left <= right, not left < right

B. The mid calculation is incorrect

C. The target comparison uses wrong operators

D. The function should return left instead of -1

Solution

1. Step 1: Analyze the loop condition

   The loop uses while(left < right), which misses checking when left equals right, possibly skipping the last element.

2. Step 2: Correct the loop condition

   Changing to while(left <= right) ensures all elements are checked, including when left == right.

3. Final Answer:

   The loop condition should be left <= right, not left < right -> Option A

4. Quick Check:

   Loop must cover all indices [OK]

Hint: Use while(left <= right) to cover all elements [OK]

Common Mistakes:

• Using while(left < right) misses last element
• Incorrect mid calculation (not here though)
• Returning wrong index when not found

5. Given a rotated sorted array with possible duplicates, which modification is needed in the binary search to correctly find the target?

const arr = [2,5,6,0,0,1,2];
function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return true;
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left++;
      right--;
    } else if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return false;
}

hard

A. Remove the duplicate elements before searching

B. Add checks to skip duplicates when left, mid, right are equal

C. Use linear search instead of binary search

D. Ignore duplicates and proceed as normal

Solution

1. Step 1: Understand duplicates impact

   Duplicates can cause ambiguity in deciding which half is sorted, breaking normal binary search logic.

2. Step 2: Skip duplicates when left, mid, right are equal

   When nums[left] == nums[mid] == nums[right], increment left and decrement right to skip duplicates and reduce search space.

3. Final Answer:

   Add checks to skip duplicates when left, mid, right are equal -> Option B

4. Quick Check:

   Skip duplicates to maintain binary search correctness [OK]

Hint: Skip duplicates when left, mid, right values match [OK]

Common Mistakes:

• Ignoring duplicates causing infinite loops
• Trying to remove duplicates before search
• Switching to linear search unnecessarily