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

Recall & Review

beginner

What is the main idea behind the binary search algorithm?

Binary search repeatedly divides a sorted list in half to find a target value quickly by comparing the middle element and deciding which half to search next.

beginner

In the iterative binary search, what variables are commonly used to track the search range?

Two variables, usually called low and high, mark the start and end of the current search range within the sorted list.

intermediate

Why is the middle index calculated as mid = low + (high - low) / 2 instead of (low + high) / 2?

Calculating mid as low + (high - low) / 2 prevents integer overflow when low and high are large numbers.

beginner

What condition ends the iterative binary search loop?

The loop ends when low becomes greater than high, meaning the target is not found in the list.

beginner

What is the time complexity of the binary search algorithm?

The time complexity is O(log n), meaning the search time grows logarithmically with the size of the list.

What must be true about the list for binary search to work correctly?

A The list must be sorted

B The list must be unsorted

C The list must contain only unique elements

D The list must be empty

Binary search requires the list to be sorted to correctly decide which half to search next.

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

A Search the left half

B Search the right half

C Return the middle index immediately

D Stop the search

If the middle element is less than the target, the search continues in the right half by moving the low pointer.

What does the variable high represent in binary search?

A The start index of the search range

B The middle index of the list

C The target value

D The end index of the search range

high marks the end index of the current search range.

What happens if the target value is not found in the list after the binary search completes?

A The function returns the last middle index

B The function throws an error

C The function returns -1 or a not found indicator

D The function returns 0

If the target is not found, the search ends and returns -1 or another indicator to show absence.

What is the advantage of using an iterative approach over a recursive approach in binary search?

A Iterative uses less memory by avoiding function call overhead

B Iterative is slower than recursive

C Iterative cannot handle large lists

D Iterative is harder to understand

Iterative binary search avoids the overhead of recursive calls, using less memory and often running faster.

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

Think about how the search range shrinks each step.

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

Consider how many elements are checked in each method.