Using binary search to find the index of an item in a sequence
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.