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")
  • 2
    \$\begingroup\$ Is the homogenous_type taken from stackoverflow.com/a/13252348/1190388 ? If so, give credits as such! \$\endgroup\$
    – hjpotter92
    Sep 13, 2018 at 11:14
  • \$\begingroup\$ Yeah it is I don't know how to credit it? \$\endgroup\$ Sep 13, 2018 at 11:20
  • 2
    \$\begingroup\$ Normally, I put them in a docstring, like: """Taken from the discussion at: <link>...""" \$\endgroup\$
    – hjpotter92
    Sep 13, 2018 at 11:23

1 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
            left = mid + 1
    if left < len(list1) and value == list1[left]:
        return left
        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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.