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).
