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.