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.

Practice

1. Why is binary search only applicable on a sorted list?

easy

A. Because it relies on dividing the list based on order to find elements quickly

B. Because it works only on lists with unique elements

C. Because it requires the list to be reversed

D. Because it compares every element one by one

Solution

1. Step 1: Understand binary search logic

   Binary search splits the list into halves and decides which half to search next based on order.

2. Step 2: Importance of sorted order

   Without sorted order, we cannot decide which half to discard, so binary search fails.

3. Final Answer:

   Because it relies on dividing the list based on order to find elements quickly -> Option A

4. Quick Check:

   Sorted list needed for binary search = Because it relies on dividing the list based on order to find elements quickly [OK]

Hint: Binary search needs order to skip half the list each step [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Believing binary search compares all elements
• Assuming binary search needs unique elements

2. Which of the following Go code snippets correctly performs binary search on a sorted slice arr to find target?

easy

A. 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

B. for i := 0; i < len(arr); i++ {
if arr[i] == target {
return i
}
}
return -1

C. left, right := 0, len(arr)
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

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

Solution

1. Step 1: Check binary search loop and boundaries

   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 correctly initializes left and right, uses <=, and updates left and right properly.

2. Step 2: Identify errors in other options

   for i := 0; i < len(arr); i++ { if arr[i] == target { return i } } return -1 is linear search, not binary. left, right := 0, len(arr) 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 has wrong boundary and updates. left, right := 0, len(arr)-1 for left <= right { mid := (left + right) / 2 if arr[mid] == target { return mid } else if arr[mid] > target { right = mid - 1 } else { left = mid - 1 } } return -1 incorrectly updates left pointer.

3. Final Answer:

   Option A code correctly implements binary search -> Option A

4. Quick Check:

   Correct binary search syntax = 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 [OK]

Hint: Binary search updates left/right pointers correctly [OK]

Common Mistakes:

• Using linear search instead of binary search
• Wrong loop conditions like < instead of <=
• Incorrectly updating left or right pointers

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
for left <= right {
  mid := (left + right) / 2
  if arr[mid] == target {
    fmt.Println(mid)
    break
  } else if arr[mid] < target {
    left = mid + 1
  } else {
    right = mid - 1
  }
}

medium

A. 0

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace binary search steps

   Initial left=0, right=4, mid=2 (value 6). arr[mid] == target, so print 2 and break.

2. Step 2: Confirm output

   The printed index is 2, which is the position of 6 in the slice.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Index of 6 in arr = 2 [OK]

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

Common Mistakes:

• Confusing index with value
• Miscomputing mid index
• Ignoring break after finding target

4. The following Go code attempts to perform binary search but does not work correctly. What is the bug?

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

medium

A. The array must be reversed before binary search

B. Loop condition should be left <= right instead of left < right

C. left and right pointers are updated incorrectly

D. mid calculation should be mid := (left + right + 1) / 2

Solution

1. Step 1: Analyze loop condition

   The loop uses left < right, which misses the case when left == right, possibly skipping the last element.

2. Step 2: Correct loop condition

   Changing to left <= right ensures all elements are checked, fixing the bug.

3. Final Answer:

   Loop condition should be left <= right instead of left < right -> Option B

4. Quick Check:

   Loop must cover all indices = Loop condition should be left <= right instead of left < right [OK]

Hint: Use <= in loop to include last element check [OK]

Common Mistakes:

• Using < instead of <= in loop condition
• Changing mid calculation unnecessarily
• Thinking array must be reversed

5. Given a sorted slice arr := []int{1, 3, 5, 7, 9, 11, 13}, you want to find the smallest element greater than or equal to target = 8. Which modification to binary search helps achieve this?

hard

A. Use linear search instead of binary search

B. When arr[mid] > target, move left to mid + 1; else move right to mid - 1

C. When arr[mid] < target, move left to mid + 1; else move right to mid - 1 and track mid as potential answer

D. Reverse the array and perform binary search

Solution

1. Step 1: Understand the problem

   We want the smallest element >= target, so we track candidates when arr[mid] >= target.

2. Step 2: Modify binary search accordingly

   If arr[mid] < target, move left to mid + 1; else move right to mid - 1 and save mid as potential answer.

3. Final Answer:

   When arr[mid] < target, move left to mid + 1; else move right to mid - 1 and track mid as potential answer -> Option C

4. Quick Check:

   Track candidate when arr[mid] >= target = When arr[mid] < target, move left to mid + 1; else move right to mid - 1 and track mid as potential answer [OK]

Hint: Track mid when arr[mid] >= target, adjust pointers accordingly [OK]

Common Mistakes:

• Not tracking potential answer index
• Moving pointers incorrectly
• Using linear search instead of binary search