0x000e - Searching Algorithms – Part 1

This is the first part of some searching algorithms that I’m implementing. The algorithms are:

Linear Search
Binary Search
Uniform Binary Search
Fibonacci Search
Jump Search
Interpolation Search
Ternary Search

In this part, Linear Search is discussed.

Linear Search

The linear/sequential search technique is the simplest of all searching algorithms and it involves checking every element, one at a time in sequence, until the desired one is found. This type of search is easy to implement, but practical when the list has few elements or the list is unsorted. The best case is when the first element is the one to be found. The worst case is when the element is not found even after searching through the entire list. Thus, both the worst-case and expected cost is asymptotically O(n). Below are some variations of the Linear Search algorithm:

1. Forward Iteration This is the simplest variation for Linear Search. According to this method, the list is traversed from the beginning for checking the occurrence of value. If found, the index is returned, otherwise a False is returned. I modified this with the addition of an attribute start, assigned 0 by default. This means that unless the user explicitly specifies an index from where the search should proceed, the searching will take place from the first element of the list. When the desired value is found, the found variable is made False. If at the end, found is still False, a message in the form of a string is returned saying that “<value> was not found in the list.” The implementation in Python is as follows:


# Returns index of the value, if found. Otherwise returns False.
def FOR_search(a_list, value, start = 0) :
    found = False
    l = len(a_list)
    if l == 0: return "List is empty."

    for index in range(start, l) :
        if a_list[index] == value:
            found = True
            return index

    if not found:
        return "%s was not found in the list." % value

2. Recursive Version The Linear Search algorithm can be constructed as a recursive algorithm. In this version, if the value is found at the first index (index 0), True is returned. Otherwise, if the list is not empty, the remainder of the list (starting form index ‘1’) is searched. If the value is not found after searching all elements, False is returned. This method is disadvantageous for large lists as a lot of stack space is required for recursive searching. The Python implementation is:


# Returns True if found, otherwise False.
def REC_search(a_list, value) :
    if len(a_list) != 0:
        if a_list[0] == value:
            return True
        else:
            a_list = a_list[1:]
            return REC_search(a_list, value)

    else: return False

3. Reverse Search A trivial variant of the Forward Iteration is the Reverse Search. Starting from the last index, elements are matched with value. If found to occur, the last index is returned, else False is returned. The Python implementation is:


# Returns last index of value if found. Otherwise returns False.
def REV_search(a_list, value) :
    i = len(a_list) - 1
    while i >= 0:
        if a_list[i] == value:
            return i
        i = i-1
    return False

4. Sentinel Search To reduce overhead of checking the list’s length, the value to be searched can be appended to the list at the end (or beginning in case of Reverse Search) as a “sentinel value”. A sentinel value is one whose presence guarantees the termination of a loop that processes structured (or sequential) data. Thus on encountering a matching value, its index is returned. The calling function can then determine if the returned index is a valid one or not. Though the optimization resulted in isn’t much, it reduces the overhead of checking if the index is within limit in each step. The Python implementation is:


# Return index of value.
def SEN_search(a_list, value) :
    a_list.append(value)
    index = 0

    while True:
        if a_list[index] == value: break
        index = index+1
    return index

5. Ordered List Search If we have a ordered list that must be searched sequentially for a value, such as linked-lists and files with variable-length records, then to improve the average performance, instead of searching the entire list, we exit on encountering an element larger than the desired one. This is because the list is an ordered/sorted one. The Python implementation is:


# Return True or False.
def ORD_search(a_list, value) :
    index = 0
    while True:
        assert index < len(a_list)
        if a_list[index] == value: return True
        elif a_list[index] > value: return False
        index = index+1
    return False