Improve this page

Searching

A sequential search in an array takes O(n) time in case of sorted data or un-sorted data both. The searching time can be further reduced by using some additional data structures like Binary Search Tree, Dictionary, etc.

Let’s suppose that the data given is in sorted order, then we can reduce the searching time even without using any additional data structure.

Let’s say you want to search an element key in the given sorted list. Also, as the data is in sorted order then we can simply have a look on to the middle element, if the key is greater than the middle element then we can say that the key is present after the middle element in the list. So we can discard the first half of the list and just focus on the second half. We again repeat the same process where we just consider the second half of the list as the main list. This process is also known as binary search.

If you observe the operations being done in order to search an element, then you can see the self-similar nature. Since we have self-similarity in the problem thus, I am gonna write a recursive solution for binary search.

• Base case: When we found the key to be present in the middle of the list or sub-list. Also, there can be a case where we don’t have key present in the list, then, in this case, the size of the list will become 0 at some point of time, so return some value to indicate that element wasn’t found.

• Recursive case: The case which is self-similar, i.e. searching will still take place in this case but on a smaller part of the list. So based on the comparison of key and middle element in the list we decide which part to strip out.

Example code

def binary_search_helper(arr, key, first, last):
    # get middle
    mid = first + (last-first)/2
    if first <= last:
        if key == arr[mid]:
            return mid
        elif key < arr[mid]:
            # present in first half
            return binary_search_helper(arr, key, first, mid-1)
        else:
            # present in second half
            return binary_search_helper(arr, key, mid+1, last)


def binary_search(arr, key):
    return binary_search_helper(arr, key, 0, len(arr)-1)


if __name__ == '__main__':
    ret = binary_search([1, 3, 5, 7, 9, 11, 13, 15, 18, 21, 45, 66, 999], 66)
    if ret is not None:
        print 'found at index: ' + str(ret)
    else:
        print 'element not found'

Ternary Search code

def ternary_search_helper(arr, left, right, key):
    if right >= left:
        # getting first partitioning index
        mid1 = left + (right - left)/3
        # getting second partitioning index
        mid2 = right - (right - left)/3

        if arr[mid1] == key:
            return mid1
        elif arr[mid2] == key:
            return mid2
        elif key < arr[mid1]:
            return ternary_search_helper(arr, left, mid1-1, key)
        elif key > arr[mid2]:
            return ternary_search_helper(arr, mid2+1, right, key)
        else:
            return ternary_search_helper(arr, mid1+1, mid2-1, key)


def ternary_search(arr, key):
    return ternary_search_helper(arr, 0, len(arr)-1, key)


if __name__ == '__main__':
    ret = ternary_search([1, 3, 4, 5, 56, 78, 7894, 56753735, 34523535345], 656646)
    if ret:
        print 'element found at index: ', ret
    else:
        print 'element not found'

Time complexity = O(log3(n))

Upper bound: Given a random number, get the next greater number present in a sorted array

Example code:

def upper_bound_iterative(arr, key):
    low, high = 0, len(arr) - 1
    res = -1
    while low <= high:
        mid = low + (high-low)/2
        if key < arr[mid]:
            res = mid
            high = mid - 1
        else:
            low = mid + 1
    return res


def upper_bound_recursive_helper(arr, key, low, high, res):
    # get mid
    mid = low + (high - low)/2
    if low <= high:
        if key < arr[mid]:
            # the key might be present in first half, but I want to find
            # the next greater element of key, so I store the mid as the
            # result, I will update the result when I see find any other
            # element which is greater than key but less than arr[mid]
            res[0] = mid
            # also, I need to update the high
            upper_bound_recursive_helper(arr, key, low, mid - 1, res)
        else:
            # key is in the second half thus, here I yet don't know which
            # element might be the just greater than key as arr[mid] is
            # smaller, so the greater element would definitely come after
            # mid index, so I don't udpate result but I need to update low
            upper_bound_recursive_helper(arr, key, mid + 1, high, res)


def upper_bound_recursive(arr, key):
    res = [-1]
    upper_bound_recursive_helper(arr, key, 0, len(arr)-1, res)
    return res[0]


if __name__ == '__main__':
    arr = [2, 3, 43, 76, 145, 345, 564]
    ind = upper_bound_iterative(arr, 444)
    if ind != -1:
        print arr[ind]
    else:
        print 'ind:', ind
    print '----------------'
    ind = upper_bound_recursive(arr, 13)
    if ind != -1:
        print arr[ind]
    else:
        print 'ind:', ind

Time complexity = O(log2(n))

Back

Next