Python – Time-consuming between linear and dichotomous searches using Python

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

I want to do these 3 things for each dimension value in a given list:

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

2. Run a sequential search against -1 in the list and record the time taken for the sequential search

A binary lookup

3. of -1 is performed in the sorted list (after sorting) and the time spent by the binary lookup is recorded

What I did was:

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 get is:

Binary search is known to be much faster than linear search.
So, I’m just wondering why it shows that binary lookups consume more time than linear lookups?

1) You need to consider the sorting time. Dichotomy lookup only works with sorted lists, so sorting takes time and its time complexity is O(nlogn). In your case, you are sorting the timer after it starts, so it will be higher.

2) You are searching for an element that does not exist in the list, i.e. -1, which is not the general case for binary searches. The worst-case scenario of a binary search would have to make so many jumps to never find the element.

3) Please don’t use list as a variable, it’s a keyword for python and you’re obviously overriding it. Use something else.

Now, if you sort the list without timing it. The results have changed dramatically. It’s 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

All I did was sort the list before timing. way, much better than you have to sort and search for it all at once.