Binary Search Iterative Approach in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the binary search iterative approach?

It repeatedly divides the sorted list in half to find the target value, by comparing the middle element and narrowing the search range until the target is found or the range is empty.

beginner

In binary search iterative approach, what happens if the middle element is less than the target?

The search continues in the right half of the list, so the start index is moved to mid + 1.

beginner

Why is binary search only applicable on sorted lists?

Because it relies on comparing the target with the middle element to decide which half to search next, which only works if the list is sorted.

intermediate

What is the time complexity of the binary search iterative approach?

O(log n), where n is the number of elements in the list, because the search space halves each step.

beginner

Show the key variables used in the binary search iterative approach and their roles.

start: the beginning index of the current search range; end: the ending index of the current search range; mid: the middle index calculated as start + (end - start) / 2; target: the value to find.

What does the binary search iterative approach do when the middle element equals the target?

A Returns the middle index as the target position

B Searches the left half of the list

C Searches the right half of the list

D Ends with failure

When the middle element matches the target, the search is successful and the middle index is returned.

Which condition ends the binary search iterative loop without finding the target?

A start == end

B start > end

C mid == target

D start < end

The loop ends when the start index passes the end index, meaning the target is not in the list.

How is the middle index calculated in binary search iterative approach to avoid overflow?

A mid = end - start

B mid = (start + end) / 2

C mid = start * end

D mid = start + (end - start) / 2

Calculating mid as start + (end - start) / 2 prevents integer overflow in some languages.

What is the first step in the binary search iterative approach?

A Check if the list is sorted

B Return -1 if list is empty

C Initialize start and end indexes

D Calculate mid index

The algorithm starts by setting start to 0 and end to the last index of the list.

If the target is smaller than the middle element, what does the binary search iterative approach do?

A Moves end to mid - 1

B Moves start to mid + 1

C Returns mid

D Ends search

If target is less than middle element, the search continues in the left half by moving end to mid - 1.

Explain step-by-step how the binary search iterative approach finds a target in a sorted list.

Think about how the search range changes each step.

Describe why binary search iterative approach is more efficient than linear search on large sorted lists.

Consider how many elements are checked in each method.

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