Question

An algorithm repeatedly divides a problem into smaller sub-problems, solves them independently, and combines the results to obtain the final solution. Determine the algorithm that follows this strategy.

• A. Linear search
• B. Binary search
• C. Breadth First search
• D. Bubble sort

Hint:

Other famous examples of Divide and Conquer include Merge Sort and Quick Sort. Remember that for Binary Search to work, the input data MUST be sorted beforehand.

Answer 1

The Correct Option is B

Concept: The strategy described is known as "Divide and Conquer." This algorithmic paradigm involves three main steps:
• Divide: Breaking the problem into smaller, similar sub-problems.
• Conquer: Solving the sub-problems (usually recursively).
• Combine: Merging the solutions of the sub-problems to get the final result.

Step 1: Analyzing the options against the strategy.

• Linear search: Simply checks every element one by one. It does not divide the problem.
• Breadth First Search (BFS): A graph traversal technique that explores neighbors level by level. It uses a queue, not a divide-and-conquer strategy.
• Bubble sort: A simple sorting algorithm that repeatedly swaps adjacent elements. It is an iterative approach.

Step 2: Identifying the Divide and Conquer approach.
Binary Search works by looking at the middle element of a sorted array. If the target is not the middle element, the algorithm "divides" the search space in half and "conquers" the relevant half, ignoring the other. This process continues recursively.

Step 3: Conclusion.
Among the choices provided, Binary Search is the only algorithm that inherently utilizes the division of the problem space to reach a solution efficiently.