Using binary search to find the index of an item in a sequence

Question

Here's my script:

def index(seq, item):
    """Returns the index of an item in an increasingly-sorted
       sequence (if exists) otherwise returns the index where
       it would be inserted, using binary search.

       seq: a sequence.

       precondition: seq is sorted increasingly.
       """
    # Updates the sequence with the item using a
    # set to avoid duplicates.
    seq = set(seq)
    seq.update([item])

    # Converts the sequence to a list and re-sorts it. 
    sorted_seq = sorted(seq)

    middle = len(sorted_seq) // 2
    middle_value = sorted_seq[middle]

    first_half = sorted_seq[:middle]
    second_half = sorted_seq[middle:]

    if item == middle_value:
        return middle

    elif item < middle_value:
        return index(first_half, item)

    elif item > middle_value:
        return index(second_half, item) + len(first_half)

How can it be refactored and optimized?

Notes:

• I'm a hobbyist and beginner (in programming in general, and Python in particular).

• I'm new to binary search I just understand the basic idea.

Answer 1

seq = set(seq)
seq.update([item])

# Converts the sequence to a list and re-sorts it. 
sorted_seq = sorted(seq)

In worst case, sorted() will take \$\Theta(n \log n)\$, where \$n = \$ len(seq). Even worse, if you did not found the value, you recur to half of the original sequence, and so on.

So, instead of presorting the sequence, just proceed to doing the actual search; if the caller fails to input a sorted list, it's not your fault.

I have this in mind, runs in worst case logarithmic time and behaves exactly as your implementation:

def binary_search(lst, value):
    count = len(lst)
    first = 0

    while count:
        it = first
        step = count // 2
        it += step
        if value > lst[it]:
            it += 1
            first = it
            count -= step + 1
        else:
            count = step

    return first


def main():
    lst = [1, 2, 5, 10, 11, 17, 20]

    for value in range(0, 25):
        print("OP:", index(lst, value))
        print("cr:", binary_search(lst, value))
        print("---")

if __name__ == "__main__":
    main()

Hope that helps.

Answer 2

seq = set(seq)

This will cause index calculations to be incorrect. Consider this invocation:

index([1, 1, 2, 3], 2)

This should return 2 but your function returns 1. As a caller of your index method, I would expect the returned index to have item in seq.

---

seq.update([item])

This is a bug. It's causing print(index([1, 1, 2, 3], 15)) to return 3, when it should return -1 or some other sentinel value to denote absence of an item in seq.

EDIT: The function's documentation clearly says that index will return the final index after insertion if item does not exist in seq.

---

sorted_seq = sorted(seq)

This is unnecessary. Validate/assume your input seq to be sorted. This should be the standard expectation from any caller invoking your index function.

---

Be careful about:

first_half = sorted_seq[:middle]
second_half = sorted_seq[middle:]

Python fortunately will not create copies of the list but other languages may create copies of the original list for this operation.

---

After you have removed seq.update([item]), you will need to check for the base of your recursion, namely when seq is empty, causing

middle_value = sorted_seq[middle]

to fail.

---

As an aside, try implementing this as an iterative algorithm.

1. It will run faster
2. The recursive version will crash for large seq.

Totally aside, have a look at Binary Search tutorial on TopCoder Its a pretty good article.