algorithmdata-structurescomputer-sciencebinary-searchdivide-and-conquer

Why is Binary Search a divide and conquer algorithm?

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?

Solution

  • The book:

    Data Structures and Algorithm Analysis in Java (2nd Edition), by Mark Allen Weiss

    Says that a D&C algorithm should have two disjoint recursive calls, just like QuickSort does.

    Binary Search does not have this, even though it can be implemented recursively.