Why Binary Search and What Sorted Order Gives You in DSA Go - Why It Works

Concept Flow - Why Binary Search and What Sorted Order Gives You

Start with sorted array

↓

Set low = 0, high = length-1

↓

Calculate mid = (low + high) / 2

↓

Compare target with array[mid

↓

Set high=mid-1

↓

Repeat until low > high

↓

Target not found

Binary search works on sorted arrays by repeatedly dividing the search range in half, comparing the target with the middle element, and narrowing down the search until the target is found or the range is empty.

Execution Sample

DSA Go

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

This code searches for a target number in a sorted array using binary search and returns its index or -1 if not found.

Execution Table

Step	Operation	low	high	mid	Compare arr[mid] with target	Action	Search Range	Result
1	Initialize	0	6	-	-	-	[2,4,6,8,10,12,14]	Continue
2	Calculate mid	0	6	3	arr[3]=8 vs target=10	8 < 10 → low=mid+1=4	[10,12,14]	Continue
3	Calculate mid	4	6	5	arr[5]=12 vs target=10	12 > 10 → high=mid-1=4	[10]	Continue
4	Calculate mid	4	4	4	arr[4]=10 vs target=10	Found target at index 4	[10]	Stop
5	Exit	-	-	-	-	-	-	Target found at index 4

💡 Search stops when target is found at index 4 or when low > high (not in this case).

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
low	0	4	4	4	4
high	6	6	4	4	4
mid	-	3	5	4	4
target	10	10	10	10	10

Key Moments - 3 Insights

Why must the array be sorted for binary search to work?

Because binary search decides which half to search next by comparing the target with the middle element. If the array is not sorted, this logic fails. See execution_table steps 2 and 3 where the search range is narrowed based on comparisons.

Why do we update 'low' to mid+1 or 'high' to mid-1 instead of mid?

Because mid has already been checked and is not the target, so we exclude it from the next search range to avoid infinite loops. This is shown in execution_table steps 2 and 3 where low or high moves past mid.

What happens if the target is not in the array?

The search range eventually becomes empty (low > high), and the function returns -1. This is the exit condition after repeating the steps without finding the target.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at step 3?

A 3

B 5

C 4

D 6

💡 Hint

Check the 'mid' column in execution_table row for step 3.

At which step does the search range narrow to just one element?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Search Range' column in execution_table to see when it reduces to one element.

If the array was not sorted, what would happen to the binary search process?

A It might miss the target because the search range decisions would be wrong.

B It would still find the target correctly.

C It would run faster.

D It would return the first element always.

💡 Hint

Refer to key_moments about why sorting is necessary.

Concept Snapshot

Binary Search requires a sorted array.
Start with low=0 and high=length-1.
Find mid = (low+high)/2.
Compare target with arr[mid].
If equal, return mid.
If target > arr[mid], search right half (low=mid+1).
Else search left half (high=mid-1).
Repeat until low > high or found.

Full Transcript

Binary search is a fast way to find a number in a sorted list. We start by looking at the middle number. If it matches the target, we are done. If the target is bigger, we look only in the right half. If smaller, we look only in the left half. We keep cutting the search area in half until we find the target or run out of numbers. This only works if the list is sorted because we rely on order to decide which half to search next.

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