Binary Search as Divide and Conquer in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the divide and conquer approach in binary search?

Divide the problem into smaller parts by splitting the array into halves, then solve the smaller part where the target might be, repeating until found or empty.

beginner

In binary search, what condition tells you to search the left half of the array?

If the target value is less than the middle element, search the left half because the array is sorted.

beginner

Why does binary search require the array to be sorted?

Because it decides which half to search based on comparisons, sorting ensures the target is only in one half, making the search efficient.

intermediate

What is the time complexity of binary search and why?

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

intermediate

Show the recursive step in binary search as divide and conquer.

Check middle element; if target equals middle, return index; else recursively search left or right half depending on comparison.

What does binary search do at each step?

A Splits the array into two halves and searches one half

B Checks every element one by one

C Sorts the array first

D Searches both halves simultaneously

Binary search divides the array into halves and searches only the half where the target could be.

Which condition means you should search the right half in binary search?

A Target is less than middle element

B Target is equal to middle element

C Target is greater than middle element

D Array is unsorted

If the target is greater than the middle element, binary search continues in the right half.

What is the base case for the recursive binary search?

A When the target is greater than all elements

B When the array is sorted

C When the array size is odd

D When the array is empty or target is found

The recursion stops when the target is found or the search space is empty.

Why is binary search faster than linear search on sorted arrays?

A Because it checks elements randomly

B Because it halves the search space each step

C Because it sorts the array first

D Because it uses more memory

Binary search halves the search space each step, reducing the number of checks quickly.

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

A It must be sorted

B It must have unique elements

C It must be unsorted

D It must be empty

Binary search requires a sorted array to decide which half to search.

Explain how binary search uses divide and conquer to find a target in a sorted array.

Think about cutting the problem size in half each time.

Describe the base case and recursive step in a recursive binary search function.

Focus on when the function stops and how it calls itself.