Why my bisection search is slower than linear search in python?

Question

I was asked during an interview to implement bisection search to improve search time and I came up with this. I came home and test it but it looks like the linear search is doing way better than my bisection search. Did I do something wrong here?

import time

sorted_list = range(0, 10000000)
needle = 9999999

def split_list(sorted_list):
    half = len(sorted_list)/2
    return sorted_list[:half], sorted_list[half:]

def bisection(haystack, needle, length_of_list):
    if len(haystack) <= length_of_list/5:
        return haystack

    first, last = split_list(haystack)
    if needle < first[-1]:
        return bisection(first, needle, length_of_list)
    else:
        return bisection(last, needle, length_of_list)

def linear_search(smaller_ist):
    for ele in smaller_list:
        if ele == needle:
            return 0

start_time = time.time()
smaller_list = bisection(sorted_list, needle, len(sorted_list))
print linear_search(smaller_list)
print("--- %s seconds ---" % (time.time() - start_time))

start_time = time.time()
print linear_search(sorted_list)
print("--- %s seconds ---" % (time.time() - start_time))

Answer 1

List slicing is O(k) where k is the length of the slice you are getting. You repeatedly slice the list in split_list(), in the line return sorted_list[:half], sorted_list[half:]. The top-level call to bisection, which calls split_list() on the entire list, will take O(n) just to run split_list (since the size of the left half + size of the right half = n), which by itself already matches the time complexity of the linear search.

One way to get around this is, instead of list slicing, pass around a lowerBound and upperBound in the recursive calls to your function (where the top-level call uses a lowerBound and upperBound set to 0 and len(sorted_list) respectively ). And length_of_list would be upperBound - lowerBound.