Efficiency Analysis of Binary Search Implementation in Python

Question

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.

Answer 1

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.

Answer 2

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. This is known to have a time complexity of O(log𝑛)

or:

• It is not 100% guaranteed that the list is sorted. In that case it makes no sense to check that it is sorted and then perform the binary search, because when you do that check, 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. Here the time complexity is O(𝑛).

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 step followed by a binary search would deteriorate the whole efficiency gain that a pure binary search delivers: the O(log𝑛) complexity of the binary search would be lost in the O(𝑛) complexity of the verification part, giving O(𝑛) as overall time complexity.