Using binary search to find the index of an item in a sequence 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 &lt; middle_value:
        return index(first_half, item)

    elif item &gt; 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.
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.


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


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