Binary Search as Divide and Conquer in DSA C - 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 conquer by searching in the half where the target might be.

beginner

In binary search, what condition decides which half of the array to search next?

Compare the target value with the middle element; if target is smaller, search left half; if larger, search right half.

beginner

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

Because binary search relies on order to decide which half to search next; without sorting, this decision is not possible.

intermediate

What is the time complexity of binary search and why?

O(log n) because each step halves the search space, quickly reducing the problem size.

intermediate

How does binary search demonstrate the divide and conquer strategy?

It divides the array into two halves and conquers by recursively searching the half that may contain the target until found or empty.

What is the first step in binary search on a sorted array?

A Find the middle element

B Sort the array

C Search the entire array linearly

D Swap elements

Binary search starts by finding the middle element to divide the array.

If the target is greater than the middle element, which part of the array do we search next?

A Right half

B Left half

C Both halves

D None

If target > middle element, search the right half because the array is sorted.

What happens if the target equals the middle element in binary search?

A Search left half

B Search right half

C Return the middle element's index

D Continue searching both halves

If target equals middle element, binary search returns its index immediately.

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

A O(n)

B O(log n)

C O(n log n)

D O(1)

Binary search halves the search space each step, leading to O(log n) complexity.

Why can't binary search be used on an unsorted array?

A Because it needs duplicates

B Because it requires linear search

C Because it only works on arrays of size 1

D Because it relies on sorted order to decide which half to search

Binary search depends on sorted order to eliminate half the array each step.

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

Think about how the array is split and how the search space shrinks.

Describe why binary search is more efficient than linear search for large sorted arrays.

Focus on how quickly the search space reduces.