binary search

binary_search.py

import math


def binary_search(haystack, needle, start=None, end=None):
    start = 0 if not start else start
    end = len(haystack) if not end else end
    midpoint = math.floor((end - start)/2) + start
    # do we match the midpoint or have only one element then we are done
    if needle == haystack[midpoint] or len(haystack[start:end]) == 1:
        return midpoint
    else:
        # if our number is less than midpoint or greater
        # then work with just that side of data
        if needle > haystack[midpoint]:
            start = midpoint+1
        elif needle < haystack[midpoint]:
            end = midpoint-1
        return binary_search(haystack, needle, start, end)


if __name__ == '__main__':
    # must be a sorted array..
    needle = 6
    print('%d index is value %d' % (binary_search([1, 4, 5, 6, 12, 33, 56, 58, 90, 101], needle), needle))