Binary Search Iterative Approach in DSA Go

Mental Model

Binary search finds a number by repeatedly cutting the search area in half until the number is found or no area remains.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is before or after that page, and repeating this until you find the word.

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers:  low ↑                 high ↑
           mid ↑

Dry Run Walkthrough

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

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

Step 1: Calculate mid index between low=0 and high=6

low=0, mid=3, high=6, array[mid]=7

Why: We check middle element 7 to decide which half to search next

Step 2: Since 9 > 7, move low to mid+1=4. Calculate mid between low=4 and high=6

low=4, mid=5, high=6, array[mid]=11

Why: Search right half because 9 is greater than 7. Now 11 > 9 so next move high left

Step 3: Since 11 > 9, high = mid - 1 = 4. Now low=4, high=4, mid=4, array[mid]=9

Found 9 at index 4

Why: Element matches the target, search ends

Result:

Index 4 where value 9 is found

Annotated Code

DSA Go

package main

import "fmt"

func binarySearchIterative(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
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

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

for low <= high {

loop until search area is empty

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

calculate middle index to split search area

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

check if middle element is the target

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

target is in right half, move low pointer

else { high = mid - 1 }

target is in left half, move high pointer

Output

Found 9 at index 4

Complexity Analysis

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

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 arrays by cutting search space repeatedly

Edge Cases

empty array

returns -1 immediately as no elements to search

DSA Go

for low <= high {

target not in array

search space shrinks until low > high, then returns -1

DSA Go

return -1

single element array with target present

finds target at index 0 quickly

DSA Go

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

When to Use This Pattern

When you need to find an element quickly in a sorted list, use binary search iterative approach because it efficiently halves the search space each step.

Common Mistakes

Mistake: Calculating mid as (low + high) which 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 space

Summary

Finds the position of a target value in a sorted array by repeatedly dividing the search range.

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

The key is to cut the search area in half each step until the target is found or no area remains.

Practice

1. What is the main purpose of the mid variable in the iterative binary search algorithm?

easy

A. To keep track of the number of iterations

B. To store the target value to search

C. To find the middle index of the current search range

D. To hold the entire array being searched

Solution

1. Step 1: Understand the role and importance of mid in binary search

   The mid variable calculates the middle index between the current low and high indices to split the search range. By checking the element at mid, the algorithm decides whether to search the left or right half next, making the search efficient.

2. Final Answer:

   To find the middle index of the current search range -> Option C

3. Quick Check:

   mid = middle index [OK]

Hint: Mid splits search range in half each step [OK]

Common Mistakes:

• Confusing mid with target value
• Using mid as a counter instead of index
• Not updating mid inside the loop

2. Which of the following is the correct way to calculate the middle index mid in Go to avoid integer overflow?

easy

A. mid := (low + high) / 2

B. mid := (high - low) / 2

C. mid := (low - high) / 2

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

Solution

1. Step 1: Understand integer overflow risk and safe calculation

   Adding low + high directly can overflow if both are large integers. Calculating mid as low + (high - low) / 2 avoids overflow by subtracting first.

2. Final Answer:

   mid := low + (high - low) / 2 -> Option D

3. Quick Check:

   Safe mid calculation avoids overflow [OK]

Hint: Use low + (high - low)/2 to prevent overflow [OK]

Common Mistakes:

• Using (low + high)/2 directly causing overflow
• Subtracting incorrectly causing negative mid
• Confusing order of operations

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

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
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

func main() {
    arr := []int{2, 4, 6, 8, 10}
    result := binarySearch(arr, 6)
    fmt.Println(result)
}

medium

A. 3

B. 2

C. -1

D. 0

Solution

1. Step 1: Trace the binary search for target 6 and verify return

   Array is [2,4,6,8,10]. Initial low=0, high=4. mid=2. arr[2]=6 matches target. Function returns mid = 2 immediately.

2. Final Answer:

   2 -> Option B

3. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: Check mid index value equals target first [OK]

Common Mistakes:

• Returning value instead of index
• Off-by-one errors in mid calculation
• Not updating low/high correctly

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

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

medium

A. The initial value of high should be len(arr) - 1

B. The loop condition should be low < high

C. The mid calculation causes overflow

D. The function should return arr[mid] instead of mid

Solution

1. Step 1: Check high initialization and correct it

   High is set to len(arr), which is out of array index range (max index is len(arr)-1). Set high to len(arr) - 1 to avoid index out of range error when accessing arr[mid].

2. Final Answer:

   The initial value of high should be len(arr) - 1 -> Option A

3. Quick Check:

   High = len(arr)-1 fixes index error [OK]

Hint: High index must be last valid array index [OK]

Common Mistakes:

• Setting high to len(arr) causing runtime error
• Using wrong loop condition
• Returning value instead of index

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

hard

A. When arr[mid] == target, update high = mid - 1 and continue searching

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

C. When arr[mid] == target, update low = mid + 1 and continue searching

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

Solution

1. Step 1: Understand duplicates issue and modify search logic

   Standard binary search returns any occurrence, not necessarily the first. When arr[mid] == target, move high to mid - 1 to continue searching left side for earlier occurrence, but store mid as potential answer.

2. Final Answer:

   When arr[mid] == target, update high = mid - 1 and continue searching -> Option A

3. Quick Check:

   Adjust high to find first occurrence [OK]

Hint: Move high left on match to find first occurrence [OK]

Common Mistakes:

• Returning immediately on first match
• Moving low right on match losing first occurrence
• Using linear search unnecessarily