Time elapsed between linear search and binary search using Python

Question

I have made two Python functions below, one for sequential (linear) search and other for binary search.

I want to do these 3 things for each size value in the given list :

1. generate a list of random integer values (between 1 to 1000,0000) for a given list size

2. run a sequential search for -1 on the list and record the time elapsed by sequential search

3. run a binary search for -1 on the sorted list (after sorting the list), and record the time elapsed by binary search

What I have done is :

def sequentialSearch(alist, item):
    pos = 0
    found = False

    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos = pos + 1

    return found

def binSearch(list, target):
    list.sort()
    return binSearchHelper(list, target, 0, len(list) - 1)

def binSearchHelper(list, target, left, right):
    if left > right:
        return False

    middle = (left + right)//2
    if list[middle] == target:
        return True
    elif list[middle] > target:
        return binSearchHelper(list, target, left, middle - 1)
    else:
        return binSearchHelper(list, target, middle + 1, right)

import random
import time
list_sizes = [10,100,1000,10000,100000,1000000]
for size in list_sizes:
    list = []
    for x in range(size):
        list.append(random.randint(1,10000000))

    sequential_search_start_time = time.time()
    sequentialSearch(list,-1)
    sequential_search_end_time = time.time()
    print("Time taken by linear search is = ",(sequential_search_end_time-sequential_search_start_time))

    binary_search_start_time = time.time()
    binSearch(list,-1)
    binary_search_end_time = time.time()
    print("Time taken by binary search is = ",(binary_search_end_time-binary_search_start_time))

    print("\n")

The output I am getting is :

As we know that binary search is much faster than the linear search. So, I just want to know why it is showing the time consumed by binary search is more than the time consumed by linear search?

Answer 1

1) You need to account for the sorting time. Binary search works only on sorted lists so sorting takes time, which takes the time complexity for it to O(nlogn). And in your case you are sorting it after the timer has started, So it will be higher.

2) You are searching for an element that doesn't exist in the list i.e -1 which is not the average case for Binary Search. Binary search's worst case has to make so many jumps just to never find the element.

3) Please do not use list as a variable it is a python's keyword and you are clearly overriding it. Use something else.

Now if you sort the list without timing it. Results change drastically. Here are mine.

Time taken by linear search is =  9.059906005859375e-06
Time taken by binary search is =  8.58306884765625e-06


Time taken by linear search is =  1.2159347534179688e-05
Time taken by binary search is =  4.5299530029296875e-06


Time taken by linear search is =  0.00011110305786132812
Time taken by binary search is =  5.9604644775390625e-06


Time taken by linear search is =  0.0011129379272460938
Time taken by binary search is =  8.344650268554688e-06


Time taken by linear search is =  0.011270761489868164
Time taken by binary search is =  1.5497207641601562e-05


Time taken by linear search is =  0.11133551597595215
Time taken by binary search is =  1.7642974853515625e-05

What I've done is just sort the list before it was timed. Way, Way better than if you had to sort it and search it all at once.