Why Binary Search and What Sorted Order Gives You in DSA Go - Quick Recap

Recall & Review

beginner

What is the main advantage of using binary search over linear search?

Binary search is much faster because it repeatedly divides the search space in half, reducing the number of comparisons from linear (n) to logarithmic (log n).

beginner

Why must the data be sorted to use binary search?

Binary search relies on the data being sorted so it can decide which half of the data to ignore after each comparison, making the search efficient.

beginner

What does 'sorted order' mean in the context of binary search?

Sorted order means the data elements are arranged in increasing or decreasing order, which allows binary search to quickly eliminate half of the remaining elements at each step.

intermediate

How does binary search reduce the search space after each comparison?

After comparing the target with the middle element, binary search discards the half where the target cannot be, focusing only on the other half.

intermediate

What is the time complexity of binary search and why?

The time complexity is O(log n) because the search space is halved with each step, quickly narrowing down to the target or concluding it is not present.

Why can't binary search be used on unsorted data?

A Because it depends on data being sorted to decide which half to search next

B Because unsorted data is always larger

C Because binary search only works on numbers

D Because unsorted data has duplicates

Binary search needs sorted data to know if it should look left or right after comparing with the middle element.

What happens to the search space after each comparison in binary search?

A It halves

B It doubles

C It stays the same

D It becomes empty

Binary search halves the search space after each comparison, making it efficient.

What is the best case time complexity of binary search?

A O(n)

B O(log n)

C O(n log n)

D O(1)

If the middle element is the target, binary search finds it immediately in O(1) time.

Which of these is a requirement for binary search?

A Data must be in a linked list

B Data must be sorted

C Data must be unsorted

D Data must be strings only

Binary search requires sorted data to function correctly.

What does sorted order allow binary search to do?

A Ignore the middle element

B Search all elements one by one

C Skip half the data after each check

D Search only the first element

Sorted order lets binary search skip half the data after each comparison.

Explain why binary search requires sorted data and how it uses this property to find an element quickly.

Think about how knowing order helps decide where to look next.

Describe the main difference in performance between linear search and binary search and why binary search is faster on sorted data.

Compare how many steps each search takes in the worst case.

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