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

Question

I was asked during the interview to conduct a search in half to improve the search time, and I came up with this. I came home and tested it, but it seems like a linear search makes the way better than my half 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 trimming is O (k), where k is the length of the resulting fragment. You re- split_list() list into split_list() , in the line return sorted_list[:half], sorted_list[half:] . A top-level bisection , which calls split_list() in the entire list, will take O (n) only to run split_list (since the size of the left half + the size of the right half = n), which in itself already corresponds to the time complexity of linear search.

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