Ordered Linear Search—Python

Ordered Linear Searche’s are a varient of Unordered Linear Search. The main difference is that this algorithm expects the search list to be sorted prior to searching. For this reason, the Ordered Linear Search can be a little more efficient than it’s Unordered varient.

Here’s the code

from random import shuffle


def ordered_linear_search(search_list, data):
    for i in range(len(search_list) - 1):
        if search_list[i] == data:
            # Return the index of the item
            return i
        elif search_list[i] > data:
            # The idea here is to fail at this
            # point because search_list isn't sorted
            return None
    # We didn't find our item, so return None
    return None


if __name__ == '__main__':
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    print('Shuffling names')
    shuffle(names)

    linda_index = ordered_linear_search(names, 'Linda Belcher')
    if linda_index:
        print('Linda Belcher found at ', str(linda_index))
    else:
        print('Linda Belcher was not found')

    teddy_index = ordered_linear_search(names, 'Teddy')
    if teddy_index:
        print('Teddy was found at ', str(teddy_index))
    else:
        print('Teddy was not found')

    print('Now sorting...')
    names.sort()

    linda_index = ordered_linear_search(names, 'Linda Belcher')
    if linda_index:
        print('Linda Belcher found at ', str(linda_index))
    else:
        print('Linda Belcher was not found')

When run, you will notice that first we do not find the name ‘Linda Belcher’ because the list is shuffled. After sorting, the search will identifiy ‘Linda Belcher’ at index 2.

Shuffling names
Linda Belcher was not found
Teddy was not found
Now sorting...
Linda Belcher found at  2
Advertisements

Unordered Linear Search—Python

There are many cases in computer programming we need to search for an element in a collection of data. The Unordered Linear Search is one of the simplest searching algorithms.

def unordered_linear_search(search_list, data):
    for i in range(len(search_list) - 1):
        if search_list[i] == data:
            # We have found the item at index i
            return i
        
    # If we got here, we didn't find the item
    return None

if __name__ == '__main__':
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    linda_index = unordered_linear_search(names, 'Linda Belcher')
    if linda_index:
        print('Linda Belcher found at ', str(linda_index))
    else:
        print('Linda Belcher was not found')

    teddy_index = unordered_linear_search(names, 'Teddy')
    if teddy_index:
        print('Teddy was found at ', str(teddy_index))
    else:
        print('Teddy was not found')

In this code, we are basically looping through the search_list object until we found a match. If we found the match, we return the index of the item’s location. Otherwise, we return Python’s None object to indicate the item wasn’t found. When run, the program will produce this output.

Linda Belcher found at  1
Teddy was not found