Binary Search Recursive Approach in DSA Typescript - 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 index > end index), meaning the target is not found, or when the middle element equals the target, meaning the search is successful.

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 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, reducing the problem size exponentially until the target is found or the search space is empty.

intermediate

How does recursion help in implementing binary search?

Recursion allows the function to call itself with a smaller search range, simplifying the code by handling the search in smaller parts until the base case is reached.

What should happen if the middle element equals the target in recursive binary search?

A Return -1

B Return the middle index

C Search the right half

D Search the left half

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

What is the first step in each recursive call of binary search?

A Calculate the middle index of the current search range

B Sort the array

C Return -1

D Swap elements

Each recursive call calculates the middle index to compare the target with the middle element.

What happens if the start index becomes greater than the end index in recursive binary search?

A Reset the indices

B Continue searching

C The target is not found, return -1

D Return the start index

When start > end, the search range is empty, so the target is not in the array.

Which of these is NOT a requirement for binary search to work correctly?

A Array must be sorted

B Search range indices must be valid

C Target must be comparable

D Array must have unique elements

Binary search works with duplicates as well; uniqueness is not required.

What is the advantage of using recursion in binary search?

A Simplifies code by handling smaller subproblems

B Makes the search faster than iterative

C Uses more memory without benefit

D Avoids calculating middle index

Recursion breaks the problem into smaller parts, making the code easier to understand and write.

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

Think about dividing the array and calling the function again with smaller parts.

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

Base cases tell the function when to stop searching.