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


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 < A[mid]$. Then we combine the knowledge that $x$ can be in $[L,mid)$ and $x$ cannot be in $[mid,R]$ to reduce our search space to $[L',R'] = [L,mid-1]$
| cite | improve this answer | |
  • $\begingroup$ But in for example Merge Sort, we do actually 'combine' the results obtained by solving sub problems. That doesn't happen here. $\endgroup$ – Shridhar R Kulkarni Mar 15 '16 at 16:09
  • $\begingroup$ @ShridharR.Kulkarni We are combining but not in the same way as in mergesort. We are able to go from $[L,R]$ to $[L, mid-1]$ only because we are able to combine the information about the possible location of $x$ obtained from the two sub problems. The way we are combining this information seems silly so your confusion regarding the combine step is justified. $\endgroup$ – Banach Tarski Mar 15 '16 at 16:12
  • 5
    $\begingroup$ @ShridharR.Kulkarni Why do we have to combine? It is called "divide and conquer" not "divide and combine." The conquer step is simply leveraging information from other partitions: whether this be recombining some calculation in another partition, or using knowledge that the desired element cannot be in another partition. $\endgroup$ – user16765 Mar 15 '16 at 18:48

There is no accepted formal definition of the divide and conquer paradigm (see this question for some suggestions), and so we must regard this paradigm as an informal concept. The main idea in divide and conquer is to split the original problem into smaller subproblems of a similar nature, and then combine them to deduce the final answer. In the case of binary search (or of quickselect), we split the original problem into one smaller subproblem. In other cases the number of subproblems is larger than two, for example Strassen's fast matrix multiplication algorithm, which splits into 7 subproblems.

Since divide and conquer is an informal concept, it is possible to disagree about what counts as divide and conquer. Describing binary search as divide and conquer is supposed to help you conceptualize the algorithms that you learn in the course. If you don't find this helpful in this case, just ignore it.

| cite | improve this answer | |

We do combine results with binary search. Each recursive call can return either a found location, or it can return None. This None value is the identity element for the combination operator ++, defined such that

result ++ None == result
None ++ result == result
(None ++ None == None, implied by the preceding)

(result can be a simple Yes, or it can be the position where the key was found.)

The key benefit of binary search on sorted data is that one of the two recursive searches is guaranteed to return None, and that one is guaranteed to do so in O(1) time. This means that for our search operation defined as

bs(A, x, x, key) = either result or None
bs(A, x, y, key) = bs(A, x, mid, key) ++ bs(A, mid, y, key)

the running time is defined by T(n) = T(n/2) + O(1) + O(1) = O(lg n), not T(n) = 2*T(n/2) + O(1) = O(n).

In practice, we are less precise and simply say that each call to bs only makes a single recursive call, ignoring what the unmade call would return. We do this to avoid the overhead of making an actual function call whose return value we can predict.

| cite | improve this answer | |
  • $\begingroup$ I don't quite understand your last paragraph. Could you clarify it, please? $\endgroup$ – Wildcard Mar 15 '16 at 23:40
  • 1
    $\begingroup$ Nobody ever implements binary search by making two recursive calls and combining the results of the two. They just compare the key to the midpoint of the range they are searching over and only recurse on the half that actually contains the key. $\endgroup$ – chepner Mar 16 '16 at 0:03
  • $\begingroup$ Aha. As opposed to a binary search on non-sorted input (if anyone were foolish enough to do that—or is there a use case for it?) which would have to be fully recursive and might as well be linear search, right? $\endgroup$ – Wildcard Mar 16 '16 at 0:04
  • 1
    $\begingroup$ Exactly; binary search on an unsorted array would look exactly like a linear search; whether it is left-to-right or right-to-left depends on whether you recurse on the left half or right half first. (If you chose which half to recurse on first at random, you'd get an interesting search order, but you'd still hit everything eventually :) ) $\endgroup$ – chepner Mar 16 '16 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.