patternMinor
Categorization of Binary search as Divide and Conquer
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}$.
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.