Binary Search Iterative Approach in DSA Go - Build from Scratch

Binary Search Iterative Approach

📖 Scenario: You have a sorted list of book IDs in a library system. You want to quickly find if a specific book ID is available using a fast search method.

🎯 Goal: Build a program that uses the iterative binary search method to find a book ID in a sorted list.

📋 What You'll Learn

Create a sorted slice of integers called bookIDs with the exact values: 101, 203, 305, 407, 509, 611, 713

Create an integer variable called target with the value 407

Implement an iterative binary search function called binarySearch that takes bookIDs and target as parameters and returns the index of target or -1 if not found

Print the result index returned by binarySearch

💡 Why This Matters

🌍 Real World

Binary search is used in many real-world applications like searching in databases, looking up words in dictionaries, or finding items in sorted lists quickly.

💼 Career

Understanding binary search is essential for software developers and engineers to write efficient search algorithms and optimize performance in applications.

1

Create the sorted list of book IDs

Create a slice of integers called bookIDs with these exact values: 101, 203, 305, 407, 509, 611, 713

DSA Go

# Create the sorted slice bookIDs with the given values
# Your code here

Hint

Use bookIDs := []int{101, 203, 305, 407, 509, 611, 713} to create the slice.

2

Set the target book ID to search

Create an integer variable called target and set it to 407

DSA Go

package main

func main() {
    bookIDs := []int{101, 203, 305, 407, 509, 611, 713}
    // Create target variable with value 407
    // Your code here
}

Hint

Use target := 407 to create the variable.

3

Implement the iterative binary search function

Write a function called binarySearch that takes a slice of integers called arr and an integer target. Use a for loop with variables left and right to search for target iteratively. Return the index if found, otherwise return -1.

DSA Go

package main

func main() {
    bookIDs := []int{101, 203, 305, 407, 509, 611, 713}
    target := 407
}

// Write binarySearch function here
// Your code here

Hint

Use a for loop with left and right pointers. Calculate mid as left + (right-left)/2. Compare arr[mid] with target and adjust left or right accordingly.

4

Print the index found by binary search

Call binarySearch with bookIDs and target and print the returned index using fmt.Println

DSA Go

package main

import "fmt"

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

func main() {
    bookIDs := []int{101, 203, 305, 407, 509, 611, 713}
    target := 407
    // Call binarySearch and print the result
    // Your code here
}

Hint

Use index := binarySearch(bookIDs, target) and then fmt.Println(index) to print the result.

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