Wednesday, March 30, 2016

Binary Search O(log N)

#!/usr/bin/python

### A recursive binary search function
def binarySort(arr,l,r,ele):
    m = (l+r)/2
    if arr[m] == ele:
        return m;
    elif arr[m] < ele:
        return binarySort (arr, m + 1, r, ele)
    else:
        return binarySort (arr, l, m - 1, ele)
    return -1
'''
##A iterative binary search function
def binarySort(arr, l, r, ele):
    while l < r:
        m = (l+r)/2;
        if arr[m] == ele:
            return m
        elif arr[m] < ele:
            l = m + 1
        else:
            r = m - 1
    return -1
'''
arr = [1,2,3,4,5,6,7]
l= 0
r= len(arr)-1
ele= 2
index = binarySort(arr, l, r, ele)
if index == -1:
    print "not found"
else:
    print "found at index -- "+str(index)

No comments:

Post a Comment