Why is Binary Search a divide and conquer algorith

Question

I was asked if a Binary Search is a divide and conquer algorithm at an exam. My answer was yes, because you divided the problem into smaller subproblems, until you reached your result.

But the examinators asked where the conquer part in it was, which I was unable to answer. They also disapproved that it actually was a divide and conquer algorithm.

But everywhere I go on the web, it says that it is, so I would like to know why, and where the conquer part of it is?

Answer 1

The Binary Search is a divide and conquer algorithm:

1) In Divide and Conquer algorithms, we try to solve a problem by solving a smaller sub problem (Divide part) and use the solution to build the solution for our bigger problem(Conquer).

2) Here our problem is to find an element in the sorted array. We can solve this by solving a similar sub problem. (We are creating sub problems here based on a decision that the element being searched is smaller or bigger than the middle element). Thus once we know that the element can not exist surely in one half, we solve a similar sub-problem in the the other half.

3) This way we recurse.

4) The conquer part here is just returning the value returned by the sub problem to the top the recursive tree

Answer 2

I think it is not divide and conquer, see first paragraph in http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

recursively breaking down a problem into two or more sub-problems which are then combined to give a solution

In binary search there is still only one problem which does just reducing data by half every step, so no conquer (merging) phase of the results is needed.

Answer 3

Binary search is tricky to describe with divide-and-conquer because the conquering step is not explicit. The result of the algorithm is the index of the needle in the haystack, and a pure D&C implementation would return the index of the needle in the smallest haystack (0 in the one-element list) and then recursively add the offsets in the larger haystacks that were divided in the divison step.

Pseudocode to explain:

function binary_search has arguments needle and haystack and returns index
    if haystack has size 1
       return 0
    else 
        divide haystack into upper and lower half
        if needle is smaller than smallest element of upper half
            return 0 + binary_search needle, lower half
        else
            return size of lower half + binary_search needle, upper half

The addition (0 + or size of lower half) is the conquer part. Most people skip it by providing indices into a larger list as arguments, and thus it is often not readily available.

Answer 4

Binary Search and Ternary Search Algorithms are based on Decrease and Conquer technique. Because, you do not divide the problem, you actually decrease the problem by dividing by 2(3 in ternary search).

Merge Sort and Quick Sort Algorithms can be given as examples of Divide and Conquer technique. You divide the problem into two subproblems and use the algorithm for these subproblems again to sort an array. But, you discard the half of array in binary search. It means you DECREASE the size of array, not divide.