HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Categorization of Binary search as Divide and Conquer

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dividesearchcategorizationbinaryandconquer

Problem

Why do we call binary search as 'Divide' and 'Conquer' strategy? It does not combine the results unlike other Divide and Conquer strategies.

Solution

This might seem silly but here we go.

Let our array be $A$ and the current range we are searching in be denoted as $[L,R]$ and let $mid = \frac{L+R}{2}$.

  • The divide step - We divide our search space into two ranges - $[L,mid-1]$ and $[mid,R]$.



  • The conquer step - Let's assume that WLOG the element $x$ that we are searching for is such that $x

Context

StackExchange Computer Science Q#54497, answer score: 9

Revisions (0)

No revisions yet.