Binary Search Recursive Approach in DSA Java - Execution Trace

Concept Flow - Binary Search Recursive Approach

Start with full array range

↓

Calculate middle index

↓

Compare target with middle element

↓

Found

↓

Return index

↓

Search left half

↓

Calculate middle index

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

Execution Sample

DSA Java

int binarySearch(int[] arr, int target, int left, int right) {
  if (left > right) return -1;
  int mid = left + (right - left) / 2;
  if (arr[mid] == target) return mid;
  if (target < arr[mid]) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

This code recursively searches for target in sorted array arr between indices left and right.

Execution Table

Step	Operation	Left	Right	Mid	Compare arr[mid] with target	Next Range	Result
1	Start search	0	6	3	arr[3]=7 vs target=5	Left half (0 to 2)
2	Recursive call	0	2	1	arr[1]=3 vs target=5	Right half (2 to 2)
3	Recursive call	2	2	2	arr[2]=5 vs target=5	Found target	Return index 2
4	Return						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	0	2	2
right	6	6	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 target is not found.

Why do we calculate mid as left + (right - left) / 2 instead of (left + right) / 2?

To avoid integer overflow when left and right are large, this calculation safely finds the middle index, as used in all steps in the execution_table.

How does recursion narrow down the search range?

Each recursive call updates left or right to mid - 1 or mid + 1 depending on comparison, shrinking the range until target is found or range is empty, as seen from steps 1 to 3.

Visual Quiz - 3 Questions

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

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Mid' column in the execution_table at step 2.

At which step does the condition left > right become true and cause the search to stop?

A Step 1

B Step 3

C Step 4

D It never becomes true

💡 Hint

Look at the 'Result' column and the exit_note in the execution_table.

If the target was 8 instead of 5, how would the next range change after step 1?

A Left half (0 to 2)

B Right half (4 to 6)

C Right half (3 to 6)

D Left half (0 to 3)

💡 Hint

Compare target with arr[mid] at step 1 and see which half is chosen.

Concept Snapshot

Binary Search Recursive Approach:
- Input: sorted array, target, left, right indices
- Base case: if left > right, return -1 (not found)
- Calculate mid = left + (right - left) / 2
- If arr[mid] == target, return mid
- If target < arr[mid], search left half recursively
- Else, search right half recursively
- Recursion narrows search range until found or empty

Full Transcript

Binary Search Recursive Approach works by repeatedly dividing the search range in half. We start with the full array range and calculate the middle index. We compare the target with the middle element. If they match, we return the index. If the target is smaller, we search the left half by calling the function recursively with updated right index. If larger, we search the right half with updated left index. The base case stops recursion when left index passes right index, meaning the target is not found. This approach efficiently finds the target in a sorted array by halving the search space each step.

Practice

1. What is the main idea behind the binary search recursive approach when searching for a value in a sorted array?

easy

A. Check every element one by one from start to end

B. Sort the array first and then search linearly

C. Divide the array into halves and search recursively in the half where the value may exist

D. Use a stack to store all elements and pop until the value is found

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 comparison.

2. Step 2: Apply recursion in binary search

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

3. Final Answer:

   Divide the array into halves and search recursively in the half where the value may exist -> Option C

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Binary search splits array, search half recursively [OK]

Common Mistakes:

• Thinking binary search checks every element
• Not using recursion or iteration to reduce search space
• Assuming array is unsorted

2. Which of the following is the correct base case condition in a recursive binary search function in Java?

easy

A. if (start < end) return -1;

B. if (start == end) return start;

C. if (array[mid] == target) return mid;

D. if (start > end) return -1;

Solution

1. Step 1: Identify base case for recursion end

   The base case ends recursion when the search space is invalid, i.e., start index is greater than end index.

2. Step 2: Confirm correct base case syntax

   Using if (start > end) return -1; correctly signals the target is not found.

3. Final Answer:

   if (start > end) return -1; -> Option D

4. Quick Check:

   Base case = start > end [OK]

Hint: Base case ends when start passes end [OK]

Common Mistakes:

• Using start == end as base case incorrectly
• Returning wrong index when target not found
• Confusing base case with target found condition

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

public class Test {
  public static int binarySearch(int[] arr, int start, int end, int target) {
    if (start > end) return -1;
    int mid = start + (end - start) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) return binarySearch(arr, start, mid - 1, target);
    else return binarySearch(arr, mid + 1, end, target);
  }
  public static void main(String[] args) {
    int[] data = {2, 4, 6, 8, 10};
    System.out.println(binarySearch(data, 0, data.length - 1, 6));
  }
}

medium

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Trace initial call and mid calculation

   Array is [2,4,6,8,10], start=0, end=4, target=6. Mid = 0 + (4-0)/2 = 2.

2. Step 2: Check if arr[mid] equals target

   arr[2] = 6 equals target 6, so return mid = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Calculate mid, compare, return index if match [OK]

Common Mistakes:

• Miscomputing mid index
• Returning wrong index when target found
• Confusing array indices

4. Identify the error in the following recursive binary search code snippet:

public static int binarySearch(int[] arr, int start, int end, int target) {
  if (start >= end) return -1;
  int mid = (start + end) / 2;
  if (arr[mid] == target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, start, mid - 1, target);
  else return binarySearch(arr, mid + 1, end, target);
}

medium

A. Base case condition should be start > end, not start >= end

B. Mid calculation should be start - end instead of start + end

C. Should return mid + 1 when target is greater

D. No error, code is correct

Solution

1. Step 1: Analyze base case condition

   Base case currently is if (start >= end) return -1;. This causes missing the case when start == end and target is at that index.

2. Step 2: Correct base case to allow checking when start == end

   Changing to if (start > end) return -1; ensures the single element at start==end is checked.

3. Final Answer:

   Base case condition should be start > end, not start >= end -> Option A

4. Quick Check:

   Base case must allow start == end check [OK]

Hint: Base case excludes start == end incorrectly [OK]

Common Mistakes:

• Using >= instead of > in base case
• Ignoring single element check
• Incorrect mid calculation

5. Given a sorted array with possible duplicate values, how can you modify the recursive binary search to find the first occurrence of a target value?

hard

A. Return mid immediately when arr[mid] == target

B. When arr[mid] == target, continue searching left half to find earlier occurrence

C. Search only the right half when arr[mid] == target

D. Use linear search after binary search to find first occurrence

Solution

1. Step 1: Understand duplicates and first occurrence

   Duplicates mean target can appear multiple times. To find first occurrence, we must check if earlier indices also have target.

2. Step 2: Modify recursive call when target found

   When arr[mid] == target, recursively search left half to find if target appears earlier. If none found, return current mid.

3. Final Answer:

   When arr[mid] == target, continue searching left half to find earlier occurrence -> Option B

4. Quick Check:

   Search left half on match for first occurrence [OK]

Hint: On match, search left half to find first occurrence [OK]

Common Mistakes:

• Returning first found index without checking left side
• Searching right half on match
• Using linear search unnecessarily