Binary Search

Listing two variants: One recursive and one iterative

# In this recursive version we are just not returning True/False. We are returning the index position 
# of the array where the match happened. We are using a global variable to note this index

idx = -1
def binSearch(V, arr, first, last):

    global idx
    mid = (first + last) / 2
    #print arr, first, last, mid

    if V == arr[mid]:
        #print 'found: ', mid
        idx = mid
        return mid

    if V < arr[mid]:
        binSearch(V, arr, 0, mid)
    if V > arr[mid]:
        binSearch(V, arr, mid+1, len(arr) - 1)

def binSearchIterative(V, arr):

    first = 0
    last = len(arr) - 1 
    found = False
    mid = -1

    while first <= last and not found:        
        mid = (first + last)/2

        if V == arr[mid]:
            found = True
        elif V < arr[mid]:
            last = mid - 1
        else:
            first = mid + 1

    #print 'found mid: ', mid
    print mid