binsearch.py

binsearch.py

#!/bin/python
# -*- coding: utf-8 -*-
def search_item_with_index_of(arr, target):
    """Scan list of integers (sorted) and retrive the smaller index using python
    standart list libary l.index().

    Args:
        arr (list): list of integers.
        target (target): The target int to lookup.

    Returns:
        tuple: bool, target_index

    """
    # define function vars
    is_found, target_index, n = False, -1, len(arr)

    # return when list is too small.
    if n == 1 and arr[n-1] != target:
        return is_found, target_index

    try:
        return True, arr.index(target)
    except ValueError as e:
        pass

    return is_found, target_index

def binary_search_item_with_index(arr, target):
    """Scan list of integers (sorted) and retrive the smaller index.
    the list most be sorted.

    the function will scan and reduce the list using low and hi indexs which
    represents the left and right bounderies of the listself.
    however the function will use iterative model so that we keep the stack constant.
    Args:
        arr (list): list of integers.
        target (target): The target int to lookup.

    Returns:
        tuple: bool, target_index

    """
    n = len(arr)
    # return is list is too small.
    if n == 1 and arr[n-1] != target:
        return False, -1

    # function vars.
    low,hi,target_index,is_found = 0,n,0,False

    # scan and reduce the list by moving index's to left or right side of the
    # list
    while (hi-low) >= 2:
        # fetch mid level
        mid = int(round((hi-low)/2))

        # edge case: when we scan last two items, we should sync the low index.
        if (hi-low) == 2:
            low += 1

        # check whether the target exist on left or right nodes.
        # keep scaning for the most left side (smaller index)

        # scan to left.
        if target <= arr[mid-1]:
            # index update.
            hi, target_index, is_found = mid-1, mid-1, True

        # scan to right
        elif target == arr[mid] or arr[mid] < target:
            if target == arr[low]: # return if found.
                return True, low
            low = (low + mid) # index update
        else:
            # update index in case of there is no match.
            hi = mid

    return is_found, target_index

if __name__ == "__main__":
    # small first index
    print binary_search_item_with_index([3,4,4,4,4,4], 3)

    # small last index
    print binary_search_item_with_index([1,1,1,1,1,1,2,2,2], 2)

    import time
    # test large list
    x = [5]*100000000
    x.append(6)

    start = time.time()
    # huge last index
    print binary_search_item_with_index(x, 6)
    print "binary_search_item_with_index duration: ", (time.time() - start) * 1000

    start = time.time()
    # huge last index
    print search_item_with_index_of(x, 6)
    print "search_item_with_index_of duration: ", (time.time() - start) * 1000