CODEWITHSUNDEEP
pythonalgorithmbinary-search-treelinear-search
DontDisplay
DontDisplay

Reputation: 11

Binary Search vs. Linear Search Strange Times

I have a list of about 100k integers and I am testing out concepts of linear vs binary search. It looks like my linear search is actually faster than my binary search. Im not sure I see why the that is though. Any insights?

It also looks like my cpu takes a major hit with the linear search.


def linear_search(big_list, element):
    """
    Iterate over an array and return the index of the first occurance of the item.

    Use to determine the time it take a standard seach to complate.
    Compare to binary search to see the difference in speed.

    % time ./searchalgo.py
    Results: time ./main.py  0.35s user 0.09s system 31% cpu 1.395 total

    """
    for i in range(len(big_list)):
        if big_list[i] == element:
            # Returning the element in the list.
            return i
    return -1

print(linear_search(big_list, 999990))

def linear_binary_search(big_list, value):
    """
    Divide and concuer approach
     - Sort the array.
     - Is the value I am searching for equal to the middle element of the array.
     - Compare is the middle element smaller orlarger than the element you are looking for?
        - If smaller then perform linear search to the right.
        - If larger then perform linear seach to the left.

    % time ./searchalgo.py
    Results:  0.57s user 0.18s system 32% cpu 2.344 total
    """
    big_list = sorted(big_list)
    left, right = 0, len(big_list) - 1
    index = (left + right) // 2
    while big_list[index] != value:
        if big_list[index] == value:
            return index
        if big_list[index] < value:
            index = index + 1
        elif big_list[index] > value:
            index = index - 1
        print(big_list[index])
# linear_binary_search(big_list, 999990)

Output of the linear search time:
./main.py  0.26s user 0.08s system 94% cpu 0.355 total


Output of the binary search time:
./main.py  0.39s user 0.11s system 45% cpu 1.103 total

Upvotes: 0

Views: 341

Answers (2)

Rajat kashyap
Rajat kashyap

Reputation: 622

your first algorithm time complexity is O(n) because of single traversal. But in case of your second traversal, first you sort the elements which takes O(nlogn) time which and then for searching it takes O(logn). So your second algorithm time complexity will be O(nlogn) + O(logn) which is greater than time complexity of your first algorithm.

Upvotes: 2

Joran Beasley
Joran Beasley

Reputation: 113978

def binary_search(sorted_list,target):
    if not sorted_list:
       return None
    mid = len(sorted_list)//2
    if sorted_list[mid] == target:
       return target
    if sorted_list[mid] < target:
       return binary_search(sorted_list[mid+1:],target)
    return binary_search(sorted_list[:mid],target)

Im pretty sure will actually correctly implement binary search recursively (which is easier for my brain to process) ... there is also the builtin bisect library that basically implements binary_search for you

Upvotes: -1

Related Questions