Binary Search Recursive Approach in DSA Go - Execution Trace

Concept Flow - Binary Search Recursive Approach

Start with full array and target

↓

Calculate middle index

↓

Compare middle element with target

↓

Found

↓

Search left half

↓

Recursive call with new range

↓

Repeat steps

Start by checking the middle element. If it matches the target, stop. Otherwise, recursively search the left or right half depending on comparison.

Execution Sample

DSA Go

func binarySearch(arr []int, target, low, high int) int {
    if low > high {
        return -1
    }
    mid := (low + high) / 2
    if arr[mid] == target {
        return mid
    } else if target < arr[mid] {
        return binarySearch(arr, target, low, mid-1)
    } else {
        return binarySearch(arr, target, mid+1, high)
    }
}

This function searches for target in a sorted array recursively by dividing the search range.

Execution Table

Step	Operation	Low	High	Mid	Compare arr[mid] with target	Action	Result/Return
1	Start search	0	6	3	arr[3]=7 vs target=5	5 < 7, search left half	Call binarySearch(arr, 5, 0, 2)
2	Recursive call	0	2	1	arr[1]=3 vs target=5	5 > 3, search right half	Call binarySearch(arr, 5, 2, 2)
3	Recursive call	2	2	2	arr[2]=5 vs target=5	Found target	Return index 2
4	Return from recursion	-	-	-	-	-	Return index 2 to previous calls
5	Return from recursion	-	-	-	-	-	Return index 2 to initial call

💡 Target found at index 2, recursion ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
low	0	0	2	2	2
high	6	2	2	2	2
mid	-	3	1	2	2
return	-	-	-	2	2

Key Moments - 3 Insights

Why do we check if low > high at the start?

This condition (seen in Step 1) stops recursion when the search range is invalid, meaning the target is not in the array.

Why do we calculate mid as (low + high) / 2?

Calculating mid this way (Step 1) splits the current search range in half, focusing the search efficiently.

How does recursion narrow down the search range?

Each recursive call (Steps 2 and 3) updates low or high to search only the left or right half, reducing the problem size.

Visual Quiz - 3 Questions

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

A 3

B 2

C 1

D 0

💡 Hint

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

At which step does the function find the target?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look for the row where 'Action' says 'Found target' in the execution_table.

If the target was 8 instead of 5, what would happen at Step 1?

A Search left half because 8 < 7

B Search right half because 8 > 7

C Return index 3 immediately

D Stop recursion because target not found

💡 Hint

Compare target with arr[mid] at Step 1 in the execution_table.

Concept Snapshot

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

Full Transcript

Binary Search Recursive Approach starts by checking the middle element of the current search range. If it matches the target, the function returns the index. If the target is smaller, the function recursively searches the left half. If larger, it searches the right half. This process repeats until the target is found or the search range is invalid (low > high), which means the target is not in the array. The execution table shows each recursive call's low, high, mid values, comparisons, and actions. The variable tracker follows how low, high, mid, and return values change step-by-step. Key moments clarify why the base condition is needed, how mid is calculated, and how recursion narrows the search. The visual quiz tests understanding of mid calculation, target finding step, and behavior when target changes.