Recursive Problem Solving

Remember the basic idea behind the binary search algorithm was to sucessively divide the problem in half. This is sometimes referred to as a "divide and conquer" approach to algorithm design, and it often leads to very efficient algorithms.

One interesting aspect of divide and conquer alorithms is that the original problem divides into subproblems that are just smaller versions of the original. To see what I mean, think about the binary search again. Initially, the range to search is the entire list. Our first step is to look at the middle item in the list. Should the middle item turn out to be the target, then we are finished. If it is not the target, we continue by performing binary search on either the top-half or the bottom half of the list.

Using this insight, we might express the binary search algorithm in another way.

Algorithm: binarySearch -- search for x in range nums[low] to nums[high]

mid = (low + high) / 2 if low > high x is not in nums elif x < nums[mid]

perform binary search for x in range nums[low] to nums[mid-1]

else perform binary search for x in range nums[mid+1] to nums[high]

Rather than using a loop, this defintion of the binary search seems to refer to itself. What is going on here? Can we actually make sense of such a thing?

Was this article helpful?

0 0

Post a comment