Binary Search as Divide and Conquer in DSA Go - Execution Trace

Concept Flow - Binary Search as Divide and Conquer

Start with sorted array and target

↓

Find middle element index

↓

Compare middle element with target

↓

Found target

↓

Search left half

↓

Repeat steps

Binary search splits the sorted array in half each time, compares the middle element to the target, and continues searching in the half where the target can be.

Execution Sample

DSA Go

func binarySearch(arr []int, target int) int {
  left, right := 0, len(arr)-1
  for left <= right {
    mid := (left + right) / 2
    if arr[mid] == target {
      return mid
    } else if arr[mid] < target {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1
}

This code searches for a target number in a sorted array by repeatedly dividing the search range in half.

Execution Table

Step	Operation	Left Index	Right Index	Mid Index	Mid Value	Comparison	Action	Array State
1	Initialize	0	6	-	-	-	Start search	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 == 9?	No, 7 < 9	No change
3	Update left	4	6	-	-	-	left = mid + 1	No change
4	Calculate mid	4	6	5	11	11 == 9?	No, 11 > 9	No change
5	Update right	4	4	-	-	-	right = mid - 1	No change
6	Calculate mid	4	4	4	9	9 == 9?	Yes, found target	No change
7	Return	4	4	4	9	-	Return index 4	No change

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
left	0	0	4	4	4	4	4
right	6	6	6	6	4	4	4
mid	-	3	-	5	-	4	4
midValue	-	7	-	11	-	9	9

Key Moments - 3 Insights

Why do we update 'left' to mid + 1 instead of mid when mid value is less than target?

Because mid value is already checked and is less than target, so target cannot be at mid index. Updating left to mid + 1 excludes mid from next search, as shown in step 3.

Why does the loop stop when left > right?

When left becomes greater than right, it means the search range is empty and target is not found. This condition stops the loop to avoid invalid search, as implied after step 7.

Why do we calculate mid as (left + right) / 2 each time?

Calculating mid this way finds the middle index of current search range, dividing the array into two halves for the next step, as seen in steps 2, 4, and 6.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'left' after step 3?

A 4

B 3

C 0

D 5

💡 Hint

Check the 'left' column in variable_tracker after step 3.

At which step does the condition 'arr[mid] == target' become true?

A Step 4

B Step 6

C Step 2

D Step 5

💡 Hint

Look at the 'Comparison' and 'Action' columns in execution_table.

If the target was 12 instead of 9, what would happen at step 5?

A right would be updated to mid - 1

B left would be updated to mid + 1

C target found at mid

D loop exits immediately

💡 Hint

Check the comparison logic and action when mid value is less than target in execution_table.

Concept Snapshot

Binary Search divides a sorted array by half each step.
Calculate mid = (left + right) / 2.
Compare mid value with target.
If equal, return mid index.
If target > mid value, search right half (left = mid + 1).
If target < mid value, search left half (right = mid - 1).
Stop when left > right (target not found).

Full Transcript

Binary search is a method to find a target value in a sorted array by repeatedly dividing the search range in half. We start with left at 0 and right at the last index. We calculate the middle index and compare the middle value with the target. If they match, we return the middle index. If the target is greater, we move left to mid + 1 to search the right half. If the target is smaller, we move right to mid - 1 to search the left half. This process repeats until the target is found or the search range is empty (left > right). This method is efficient because it reduces the search space by half each time.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. It uses recursion to add elements to the array.

B. It searches every element one by one until the target is found.

C. It divides the search range in half each time to find the target efficiently.

D. It sorts the array before searching for the target.

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search splits the search space into two halves and discards one half each time.

2. Step 2: Identify the efficiency of halving the search space

   By halving the range repeatedly, it quickly narrows down to the target element.

3. Final Answer:

   It divides the search range in half each time to find the target efficiently. -> Option C

4. Quick Check:

   Divide and conquer means halving search space [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Thinking binary search checks every element
• Confusing sorting with searching
• Believing binary search adds elements

2. Which of the following is the correct Go syntax to start a binary search loop on a sorted slice arr?

easy

A. for left := 0; left < len(arr); left++ { }

B. for i := 0; i < len(arr); i++ { }

C. while left < right { }

D. for left, right := 0, len(arr)-1; left <= right; { }

Solution

1. Step 1: Identify Go for-loop syntax for binary search

   Binary search uses two pointers, left and right, initialized to start and end indices.

2. Step 2: Confirm loop condition and initialization

   The loop continues while left <= right, using Go's for syntax with multiple variables.

3. Final Answer:

   for left, right := 0, len(arr)-1; left <= right; { } -> Option D

4. Quick Check:

   Go for-loop with two vars and condition [OK]

Hint: Binary search loop uses two pointers and condition left <= right [OK]

Common Mistakes:

• Using for-loop with single index only
• Using while syntax (not valid in Go)
• Incorrect loop condition like left < right

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

arr := []int{2, 4, 6, 8, 10}
target := 6
left, right := 0, len(arr)-1
found := false
for left <= right {
  mid := left + (right-left)/2
  if arr[mid] == target {
    found = true
    break
  } else if arr[mid] < target {
    left = mid + 1
  } else {
    right = mid - 1
  }
}
fmt.Println(found)

medium

A. false

B. true

C. 6

D. runtime error

Solution

1. Step 1: Trace the binary search steps for target 6

   Initial left=0, right=4, mid=2 (arr[2]=6), matches target, so found=true.

2. Step 2: Confirm loop breaks and prints found

   Loop breaks immediately after finding target, so prints true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Target found at mid index 2 [OK]

Hint: Check mid element equals target first [OK]

Common Mistakes:

• Not updating left or right correctly
• Off-by-one errors in mid calculation
• Assuming output is the target value

4. Identify the bug in this binary search Go code snippet:

arr := []int{1, 3, 5, 7, 9}
target := 4
left, right := 0, len(arr)
for left <= right {
  mid := (left + right) / 2
  if arr[mid] == target {
    fmt.Println("Found")
    break
  } else if arr[mid] < target {
    left = mid + 1
  } else {
    right = mid - 1
  }
}

medium

A. right should be initialized to len(arr)-1, not len(arr)

B. mid calculation should be mid := left - right

C. left should be incremented by 2 instead of 1

D. The loop condition should be left < right

Solution

1. Step 1: Check initialization of right pointer

   right is set to len(arr), which is out of valid index range (max index is len(arr)-1).

2. Step 2: Correct right initialization and explain impact

   Setting right to len(arr)-1 fixes out-of-range error when accessing arr[mid].

3. Final Answer:

   right should be initialized to len(arr)-1, not len(arr) -> Option A

4. Quick Check:

   Array indices go from 0 to len(arr)-1 [OK]

Hint: Initialize right to last valid index len(arr)-1 [OK]

Common Mistakes:

• Using len(arr) as index causes runtime error
• Wrong mid calculation formula
• Incorrect loop condition causing infinite loop

5. Given a sorted slice arr := []int{1, 2, 2, 2, 3, 4}, how can you modify binary search to find the first occurrence of 2?

hard

A. After finding 2, continue searching left half to find earlier occurrence

B. Return immediately when 2 is found at any position

C. Search the right half after finding 2 to find last occurrence

D. Use linear search instead of binary search

Solution

1. Step 1: Understand the problem of duplicates in binary search

   Standard binary search returns any occurrence, not necessarily the first.

2. Step 2: Modify search to continue left after finding target

   When target found, update result and move right pointer to mid-1 to find earlier occurrence.

3. Final Answer:

   After finding 2, continue searching left half to find earlier occurrence -> Option A

4. Quick Check:

   Find first occurrence by searching left side after match [OK]

Hint: Keep searching left half after finding target to get first occurrence [OK]

Common Mistakes:

• Stopping at first found occurrence
• Searching right half instead of left
• Using linear search unnecessarily