Does binary search use the divide-and-conquer strategy?
- LeslieLv 79 years agoFavorite Answer
Binary search is a divide-and-conquer (D&C) strategy.It first compares the query key q with the "middle element".
if equal, we are done.
Otherwise, it divides the range into two parts.
One part does not have the answer,
while the other part can be searched for q recursively,
until it is found or fails to exist (the part contains no element).This kind of divide-and-conquer has a special name: Decrease-and-Conquer.
On the case of binary search, it is a decrease-by-half D&C.