## Example 3: Binary Search

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: