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

Recall & Review

beginner

What is the main idea behind the binary search algorithm?

Binary search finds an item in a sorted list by repeatedly dividing the search interval in half, checking the middle element, and deciding which half to search next.

beginner

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

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

beginner

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

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

intermediate

What parameters are typically passed in a recursive binary search function?

The function usually takes the array, the target value, the start index, and the end index to define the current search interval.

intermediate

How does the recursive binary search reduce the problem size at each step?

It calculates the middle index and then calls itself on either the left half or the right half of the array, effectively halving the search space each time.

What is the time complexity of binary search in the worst case?

A O(n log n)

B O(n)

C O(log n)

D O(1)

Binary search divides the search space in half each time, leading to a logarithmic time complexity O(log n).

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

A Search the left half

B Search the right half

C Return -1 immediately

D Return the middle index

If the target is less than the middle element, the search continues recursively on the left half.

Which of these is NOT a parameter in a typical recursive binary search function?

A Start and end indices of the search range

B Target value

C Array to search

D Current index of the target

The current index of the target is not known beforehand; the function uses start and end indices to narrow the search.

What should the recursive binary search function return if the target is not found?

A The middle index

B -1 or a sentinel value

C 0

D The start index

Returning -1 or a sentinel value indicates the target is not present in the array.

Why is recursion useful in binary search?

A It makes the code shorter and easier to understand by breaking the problem into smaller parts.

B It makes the search faster than iterative methods.

C It avoids the need for a sorted array.

D It uses more memory but less CPU.

Recursion simplifies the code by handling smaller subproblems, though iterative binary search can be equally efficient.

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

Think about how the problem size reduces each time.

Describe the base cases in recursive binary search and why they are important.

Base cases stop the recursion and give the answer.