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.