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

Recall & Review

beginner

What is the main idea behind the binary search algorithm?

Binary search works by repeatedly dividing a sorted list in half to find a target value quickly. It compares the target with the middle element and decides which half to search next.

beginner

In the recursive binary search, what are the base cases?

The base cases are when the search range is empty (start > end), meaning the target is not found, or when the middle element equals the target, meaning the search is successful.

beginner

Why must the input list be sorted for binary search to work?

Because binary search decides which half to search based on comparisons, the list must be sorted to ensure that all smaller elements are on one side and larger on the other.

intermediate

What is the time complexity of binary search and why?

The time complexity is O(log n) because each step cuts the search space in half, quickly reducing the number of elements to check.

intermediate

How does recursion help in implementing binary search?

Recursion simplifies the code by letting the function call itself with a smaller search range until it finds the target or the range is empty.

What should happen if the middle element is equal to the target in recursive binary search?

A Return -1

B Search the left half

C Return the middle index

D Search the right half

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

What condition ends the recursive binary search when the target is not found?

A middle < target

B start == end

C middle == target

D start > end

When the start index becomes greater than the end index, it means the search range is empty and the target is not in the list.

Which of these is required for binary search to work correctly?

A The list must be sorted

B The list must be unsorted

C The list must contain duplicates

D The list must be empty

Binary search requires a sorted list to decide which half to search next.

What is the time complexity of binary search?

A O(n)

B O(log n)

C O(n^2)

D O(1)

Binary search cuts the search space in half each step, leading to O(log n) time complexity.

In recursive binary search, what parameters typically change with each recursive call?

A The search range (start and end indices)

B The target value

C The entire list

D The middle element

Each recursive call narrows the search range by updating the start or end index.

Explain how recursive binary search works step-by-step on a sorted list.

Think about how the list is split and how the function calls itself.

Describe why the list must be sorted for binary search and what happens if it is not.

Consider how binary search decides which half to search next.