binary search passing list slice instead of whole list

user_7216082 0
Viewed 1244

Is this binary search of the sorted list going to be faster if we pass list slice instead of the whole list, where the list has millions of items?

Normal:

def binary_search(data, target, low, high):
if low > high:
    return False
else:
    mid = (low + high) // 2
    if target == data[mid]:
        return True
    elif target < data[mid]:
        return binary_search(data, target, low, mid-1)
    else:
        return binary_search(data, target, mid+1, high)

With list slice(I had to modify it a bit):

def binary_search(data, target, low, high):
if low > high:
    return False
else:
    mid = (low + high) // 2
    if target == data[mid]:
        return True
    elif target < data[mid]:
        return binary_search(data[low:mid-1], target, 0, mid)
    else:
        return binary_search(data[mid+1:high], target, 0, high-mid)

I am currently learning about algorithms so i really don't know if this is the best practice or not.

binary-search list algorithm python
2 Answers

the problem with the second approach is that such slicing creates another list object at each iteration from the original list which means:

  • memory allocation
  • memory copy from original list

So indexing may become clearer, but performance is actually degraded, resulting to the inverse of the searched effect.

user_64515730

I think with the second approach the TimeComplexity is the same as with Normal Binary Search but Space complexity is unnecessary increasing..

Your first binary search takes constant O(1) space, meaning that the space taken by the algorithm is the same for any number of elements in the array. But in your second case space complexity is unnecessary increased by O(logn) hence it's inefficient.

user_66820710
Related