Why is Binary Search a divide and conquer algorithm?

algorithm data-structures computer-science binary-search divide-and-conquer
Kenci picture Kenci · Jan 13, 2012 · Viewed 27.8k times · Source

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

Kenci picture Kenci · Jan 13, 2012

The book

Data Structures and Algorithm Analysis in Java, 2nd edtition, Mark Allen Weiss

Says that a D&C algorithm should have two disjoint recursive calls. I.e like QuickSort. Binary Search does not have this, even if it can be implemented recursively, so I guess this is the answer.

Related questions

How to implement a queue using two stacks?

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

Read More
How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a …

Read More
What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More