Binary Search Recursive Approach in DSA Typescript - Execution Trace

Concept Flow - Binary Search Recursive Approach

Start with full array and target

↓

Calculate middle index

↓

Compare middle element with target

↓

Search left half

↓

Return result

The recursive binary search splits the array, compares the middle element with the target, then searches left or right half recursively until found or empty.

Execution Sample

DSA Typescript

function binarySearch(arr: number[], target: number, left: number, right: number): number {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

This code recursively searches for target in a sorted array by dividing the search range in half each time.

Execution Table

Step	Operation	Left	Right	Mid	Compare arr[mid] with target	Next Call Range	Result
1	Start search	0	6	3	arr[3]=7 vs target=5: 7 > 5	Search left half (0 to 2)
2	Recursive call	0	2	1	arr[1]=3 vs target=5: 3 < 5	Search right half (2 to 2)
3	Recursive call	2	2	2	arr[2]=5 vs target=5: equal	Found target at index 2	2
4	Return result						2

💡 Target found at index 2, recursion ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
left	0	0	2	2	2
right	6	2	2	2	2
mid		3	1	2	2
result				2	2

Key Moments - 3 Insights

Why do we check if left > right at the start?

Because when left passes right, it means the search range is empty and the target is not found. This is shown in step 1 where if left > right, we return -1 to stop recursion.

Why do we calculate mid as Math.floor((left + right) / 2)?

We pick the middle index to split the array into two halves. Using floor ensures mid is an integer index. This is shown in steps 1-3 where mid changes as the search range changes.

How does recursion narrow down the search range?

Each recursive call updates left or right to mid-1 or mid+1 depending on comparison, reducing the search space. See steps 1 and 2 where next call ranges shrink towards the target.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of mid at step 2?

A 2

B 3

C 1

D 0

💡 Hint

Check the 'Mid' column in row for step 2 in the execution_table.

At which step does the function find the target?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Compare arr[mid] with target' and 'Result' columns to see when target is found.

If the target was 8 instead of 5, what would be the next call range after step 1?

A Search right half (4 to 6)

B Search right half (3 to 6)

C Search left half (0 to 2)

D Search left half (0 to 3)

💡 Hint

Compare arr[mid]=7 with target=8 at step 1 and see which half is searched next.

Concept Snapshot

Binary Search Recursive Approach:
- Input: sorted array, target, left index, right index
- Calculate mid = floor((left + right)/2)
- If arr[mid] == target, return mid
- If arr[mid] > target, search left half (left to mid-1)
- Else search right half (mid+1 to right)
- Stop when left > right (target not found)

Full Transcript

Binary Search Recursive Approach splits a sorted array by comparing the middle element to the target. If equal, it returns the index. If the middle element is greater, it searches the left half recursively. If smaller, it searches the right half recursively. The recursion stops when the search range is empty (left > right). This method efficiently finds the target or returns -1 if not found.

Practice

1. What is the main idea behind the binary search recursive approach?

easy

A. Search each element one by one from start to end

B. Divide the array into halves and search recursively in the correct half

C. Sort the array after each recursive call

D. Use a queue to store elements for searching

Solution

1. Step 1: Understand binary search logic

   Binary search works by dividing the sorted array into two halves and deciding which half to search next based on the middle element.

2. Step 2: Apply recursion in binary search

   The recursive approach calls the same function on the half where the target might be, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the correct half -> Option B

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Remember: binary search splits array, then recurses [OK]

Common Mistakes:

• Thinking binary search checks every element
• Sorting array inside recursion
• Using linear search logic

2. Which of the following is the correct TypeScript function signature for a recursive binary search?

easy

A. function binarySearch(arr: number[], target: string): boolean

B. function binarySearch(arr: string[], target: number): number

C. function binarySearch(arr: number[], target: number, left: number, right: number): number

D. function binarySearch(arr: number[], target: number): void

Solution

1. Step 1: Check parameters needed for recursion

   Recursive binary search needs the array, target, and the current left and right indices to search between.

2. Step 2: Verify return type

   The function returns the index of the target if found, so the return type is number.

3. Final Answer:

   function binarySearch(arr: number[], target: number, left: number, right: number): number -> Option C

4. Quick Check:

   Parameters + return type match recursive binary search [OK]

Hint: Recursive binary search needs left and right indices [OK]

Common Mistakes:

• Missing left and right parameters
• Wrong return type (void or boolean)
• Mismatched array and target types

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

function binarySearch(arr: number[], target: number, left: number, right: number): number {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

const nums = [2, 4, 6, 8, 10];
console.log(binarySearch(nums, 6, 0, nums.length - 1));

medium

A. 2

B. 1

C. -1

D. 3

Solution

1. Step 1: Identify middle index and compare

   Initial call: left=0, right=4, mid=2. arr[2] = 6 matches target 6.

2. Step 2: Return index when found

   Since arr[mid] equals target, function returns mid = 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Check middle element first, then recurse [OK]

Common Mistakes:

• Miscomputing mid index
• Returning wrong index
• Confusing array values with indices

4. Find the error in this recursive binary search function:

function binarySearch(arr: number[], target: number, left: number, right: number): number {
  if (left >= right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

medium

A. The base case condition should be left > right, not left >= right

B. The mid calculation is incorrect

C. The function should return boolean instead of number

D. The recursive calls have wrong parameters

Solution

1. Step 1: Analyze base case condition

   The base case currently returns -1 if left >= right, but it should allow left == right to check that element.

2. Step 2: Correct base case to left > right

   Changing to left > right ensures the search includes the last element before stopping.

3. Final Answer:

   The base case condition should be left > right, not left >= right -> Option A

4. Quick Check:

   Base case must allow left == right [OK]

Hint: Base case stops when left passes right, not equals [OK]

Common Mistakes:

• Stopping search too early with wrong base case
• Miscomputing mid index
• Wrong return type

5. Given a sorted array arr = [1, 3, 5, 7, 9, 11, 13], write a recursive binary search call to find the index of 7. What will be the sequence of mid indices checked?

hard

A. [3, 5]

B. [3, 1]

C. [3, 1, 2]

D. [3]

Solution

1. Step 1: Calculate initial mid index

   left=0, right=6, mid = floor((0+6)/2) = 3. arr[3] = 7 matches target immediately.

2. Step 2: No further recursive calls needed

   Since target found at first mid, no other mid indices are checked.

3. Final Answer:

   [3] -> Option D

4. Quick Check:

   Target found at first mid index 3 [OK]

Hint: First mid often finds target if array is balanced [OK]

Common Mistakes:

• Assuming multiple recursive calls always happen
• Miscomputing mid index
• Confusing indices with values