Binary Search Python

Question

Tried to make a binary search algorithm, how did I do?

def homogeneous_type(list1):
    i_list = iter(list1)
    listtype = type(next(i_list))
    return True if all(isinstance(x, listtype) for x in i_list) else False


def binSearch(list1, value):

    if not list1:
        raise ValueError("list is empty") 
    if not homogeneous_type(list1):
        raise ValueError("list must be one type")

    left = 0
    right = len(list1) - 1
    list1 = sorted(list1)

    while left <= right:

        midIndex, mod = divmod(left + right, 2)
        midIndex = midIndex + 1 if mod else midIndex

        if list1[midIndex] == value:
            return midIndex
        elif list1[midIndex] < value:
            left = midIndex + 1
        elif list1[midIndex] > value:
            right = midIndex - 1

    raise ValueError("value not in List")

Answer 1

1. There are no docstrings. What do homogeneous_type and binSearch do?

2. In Python we rarely need to insist that lists be homogeneous. It often makes sense to have heterogeneous lists, provided that all elements support the required operations, for example it can be reasonable to have a list containing a mixture of int and float.

3. Checking that the list is homogeneous requires looking at every value to check that it is the required type. But if you are going to look at every value, you don't gain anything by doing a binary search, you might as well just call list1.index(value).

4. Similarly, sorting the list requires looking at every element, so again, there is no point in sorting and then doing a binary search. Skipping the sort and calling list1.index(value) would be faster.

5. The binary search code maintains a closed interval left <= i <= right that contains the index of the value being searched for. But maintaining a closed interval requires some complexity when computing the middle index:

   midIndex, mod = divmod(left + right, 2)
   midIndex = midIndex + 1 if mod else midIndex
   

   It would be simpler to maintain a half-open interval left <= i < right by starting with right = len(list1). Then the computation of the midpoint is simple:

   midIndex = (left + right) // 2
   

   (In the half-open version of the code the loop condition needs to be left < right rather than left <= right, and you need to assign right = midIndex rather than right = midIndex - 1.)

6. On each iteration of the binary search loop there are three comparisons:

   list1[midIndex] == value:
   list1[midIndex] < value:
   list1[midIndex] > value:
   

   This can be reduced to one comparison per iteration, like this:

   left, right = 0, len(list1)
   while left < right:
       mid = (left + right) // 2
       if value < list1[mid]:
           right = mid
       else:
           left = mid + 1
   if left < len(list1) and value == list1[left]:
       return left
   else:
       raise ValueError("not found")
   

   Note that this version of the code works fine even if list1 is the empty list, allowing you to remove the special case for if not list:.

7. Binary search is built into Python: see the bisect module.