Efficiency Analysis of Binary Search Implementation in Python-CodePudding

I have completed an iterative implementation of Binary Search in python and was wondering if there is an efficient way to ensure that your input is always sorted before sorting it if needed. How can one validate the input to be sorted? What is the time complexity if the input is not sorted? I would also appreciate comments if this code can be made more efficient.

def binary_search(array, search):
    low = 0
    high = len(array)

    while low <= high and len(array[low:high]):
        mid = (low   high) // 2
        if array[mid] == search:
            return "Found "   str(search)   " at index "   str(mid)
        elif search > array[mid]:
            low = mid   1
        elif search < array[mid]:
            high = mid - 1

    return str(search)   " not found."


search_through = [2, 3, 4, 10, 40]
to_search = 49
print(binary_search(search_through, to_search))

Output: 49 not found.

CodePudding user response：

To check "sortedness", you need to compare all pairs of successive elements. You cannot do faster than O(N) because every element counts.

Your function always takes O(Log(N)) time, because it halves the interval until it becomes a singleton. But of course, the returned value can be meaningless.

The function performs a three-way comparison, so in many cases two tests per iteration. Even though comparison for equality can cause early termination, it is unsure that this is faster than a version with two-way comparisons only.

For a O(Log(N)) process, efficiency is not so critical.

CodePudding user response：

There are two scenarios to consider. Either:

The caller of the function guarantees that the list is sorted. In that case it is not necessary to have it double checked. It is then a documented requirement of your function, and the caller will stick to it. You can do the binary search assuming the list is sorted.

or:

It is not 100% guaranteed that the list is sorted. In that case it makes no sense to check that is sorted, because when you do that, you have to visit every element of the list, which would give you the opportunity to immediately find the searched value in that list. So again, it would not be necessary to check that the list is sorted. Instead you would just use that time to actually find the value with a linear search that does not need the input to be sorted.

So in either case, it makes no sense to verify that the list is sorted. Doing that is a waste of time, as then you might as well use that iteration to look for the value and forget about the binary search all together. A binary search is only useful when it is guaranteed that the input is sorted. There should be no need to verify that -- it should be trusted that it is the case. A verification would deteriorate the whole efficiency gain that a pure binary search delivers.