Why Binary Search and What Sorted Order Gives You in DSA Go - Why This Pattern

Mental Model

Binary search quickly finds a value by repeatedly cutting the search area in half, but it only works if the list is sorted.

Analogy: Imagine looking for a word in a dictionary. Because the words are in alphabetical order, you can open near the middle, decide which half to search next, and keep narrowing down quickly.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15]
Indices:      0      1      2      3      4       5       6       7

Dry Run Walkthrough

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

Goal: Find the position of 9 quickly using binary search

Step 1: Check middle element at index 3 (value 7)

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> [15]

Why: We start by looking at the middle to decide which half to search next

Step 2: Since 9 > 7, search right half: indices 4 to 7

[9] -> [11] -> [13] -> [15]

Why: Because 9 is bigger than 7, it must be in the right half

Step 3: Check middle element at index 5 (value 11)

[9] -> [11↑] -> [13] -> [15]

Why: Look at middle of the right half to narrow down further

Step 4: Since 9 < 11, search left half: index 4

[9↑]

Why: 9 is smaller than 11, so it must be to the left

Step 5: Check element at index 4 (value 9), found target

[9↑]

Why: We found the value we were searching for

Result:

Final found position: index 4, value 9

Annotated Code

DSA Go

package main

import "fmt"

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

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

mid := left + (right-left)/2

Calculate middle index to split search space

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

Check if middle element is the target

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

If target is bigger, move left pointer to right half

else { right = mid - 1 }

If target is smaller, move right pointer to left half

Output

Found 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space, quickly narrowing down to the target

Space: O(1) because it uses only a few variables regardless of input size

vs Alternative: Compared to linear search's O(n), binary search is much faster on large sorted lists because it skips half the elements each step

Edge Cases

empty array

returns -1 immediately because there is nothing to search

DSA Go

for left <= right {

target smaller than all elements

search narrows down and returns -1 as target is not found

DSA Go

for left <= right {

target larger than all elements

search narrows down and returns -1 as target is not found

DSA Go

for left <= right {

When to Use This Pattern

When you need to find an item quickly in a sorted list, reach for binary search because it cuts the search area in half each time, making it very fast.

Common Mistakes

Mistake: Not checking if the list is sorted before using binary search
Fix: Always ensure the input list is sorted, or sort it first before applying binary search

Mistake: Calculating middle index as (left + right) which can cause integer overflow
Fix: Calculate middle as left + (right - left) / 2 to avoid overflow

Mistake: Using <= or < incorrectly in loop conditions causing infinite loops or missed elements
Fix: Use 'left <= right' as loop condition and update pointers carefully to avoid skipping elements

Summary

Binary search finds a target value quickly by repeatedly dividing a sorted list in half.

Use it when you have a sorted list and want to find an element efficiently.

The key insight is that sorted order lets you ignore half the list each step, making search very fast.