lundi 5 novembre 2018

Time elapsed between linear search and binary search using python

I need some help with my python code.

I have made two function 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 :

enter image description here

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 ?




Aucun commentaire:

Enregistrer un commentaire