In other posts we discussed the problem of searching for an item in a sorted list and described a solution based on binary search. A non-recursive program based on binary search is presented in *Algorithms – Solving Problems » Example 4: Searching for an item in a list. *

The following code contains a recursive and non-recursive version of binary search. The programs have a similar overall structure:

- the non-recursive function searchTarget contains a while loop in which each iteration proceeds on either the left of right half of the current list
- the recursive function searchTargetRecur recurses on either the right of left half of the current list.

##binarySearch.py ##binarySearch non-recursion def searchTarget(target, start, end, theList): position = -1 while start <= end: checkpoint = (start + end ) // 2 if theList[checkpoint] == target: position = checkpoint break if theList[checkpoint] < target: start = checkpoint + 1 if theList[checkpoint] > target: end = checkpoint - 1 return position ##binarySearch recursive def searchTargetRecur(target, start, end, theList): if start <= end: checkpoint = (start + end ) // 2 if theList[checkpoint] == target: return checkpoint # done! element found elif theList[checkpoint] < target: return searchTargetRecur(target,checkpoint + 1,end, theList) else: return searchTargetRecur(target,start,checkpoint - 1, theList) else: return -1 # item not found target = 150 MyList = [1, 12, 15, 44, 47, 88, 90, 92, 140, 150, 200, 300, 303, 550, 966, 980] start = 0 end = len(MyList) - 1 print "Element was found at position: ",searchTarget(target, start, end, MyList) print "Element was found at position: ",searchTargetRecur(target, start, end, MyList)

Many students find binary search intuitive and easy to understand. It is a version of recursion where the recursive call provides the final answer and no subproblems need to be combined (as done in the sorting examples).