Binary Search as Divide and Conquer in DSA Go

Mental Model

Binary search splits a sorted list into halves repeatedly to find a target quickly.

Analogy: Like guessing a number between 1 and 100 by asking if it is higher or lower than the middle number each time.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indices:     0  1  2  3  4   5   6
Search range: low -> mid -> high

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], target: 9

Goal: Find the index of target 9 in the array using binary search

Step 1: Calculate mid index between low=0 and high=6 -> mid=3, check value 7

[1, 3, 5, 7, 9, 11, 13]
low=0, mid=3(7), high=6

Why: We start by checking the middle element to decide which half to search next

Step 2: Since 9 > 7, move low to mid+1=4 to search right half

[1, 3, 5, 7, 9, 11, 13]
low=4, high=6

Why: Target is greater than mid value, so it must be in the right half

Step 3: Calculate mid between low=4 and high=6 -> mid=5, check value 11

[1, 3, 5, 7, 9, 11, 13]
low=4, mid=5(11), high=6

Why: Check middle of the new search range to narrow down further

Step 4: Since 9 < 11, move high to mid-1=4 to search left half

[1, 3, 5, 7, 9, 11, 13]
low=4, high=4

Why: Target is less than mid value, so it must be in the left half

Step 5: Calculate mid between low=4 and high=4 -> mid=4, check value 9

[1, 3, 5, 7, 9, 11, 13]
low=4, mid=4(9), high=4

Why: Only one element left to check, which matches the target

Result:

Final state: [1, 3, 5, 7, 9, 11, 13]
Target 9 found at index 4

Annotated Code

DSA Go

package main

import "fmt"

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

func main() {
    arr := []int{1, 3, 5, 7, 9, 11, 13}
    target := 9
    index := binarySearch(arr, target)
    if index != -1 {
        fmt.Printf("Target %d found at index %d\n", target, index)
    } else {
        fmt.Printf("Target %d not found\n", target)
    }
}

mid := low + (high-low)/2

Calculate middle index to split search range

if arr[mid] == target { return mid }

Check if middle element is the target

else if arr[mid] < target { low = mid + 1 }

If target is greater, move low pointer to right half

else { high = mid - 1 }

If target is smaller, move high pointer to left half

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted data by dividing the problem repeatedly

Edge Cases

empty array

returns -1 immediately as target cannot be found

DSA Go

for low <= high {

target smaller than all elements

search narrows and returns -1 after checking all possibilities

DSA Go

for low <= high {

target larger than all elements

search narrows and returns -1 after checking all possibilities

DSA Go

for low <= high {

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it divides the problem in half each time.

Common Mistakes

Mistake: Calculating mid as (low + high) can cause integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not updating low or high correctly causing infinite loop
Fix: Ensure low = mid + 1 or high = mid - 1 to shrink search range

Summary

Binary search finds a target in a sorted list by repeatedly dividing the search range in half.

Use it when you have a sorted list and want fast search performance.

The key insight is to compare the middle element and discard half the list each step.

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