iterative binary_search Python implementation

Question

I did a Python implementation of binary search implementation iteratively. It passes all of the test and I was wondering if I can get any feedback.

#!python

def binary_search_iterative(array, item):
    """iteratively return the index of the item with binary search or None if not found"""
    # Sorted array that has to be the condition
    # go through several iteration until we found this
    # First, set the lower_index = 0
    # upper_index as the length of array -1
    lower_index = 0
    upper_index = len(array) - 1
    # iteration until it is found
    while lower_index <= upper_index:
        # calculate the middle index by sum the lower_index and upper_index and divide by 2
        middle_index = (lower_index + upper_index) // 2 # // is int division
        # check if the item is found
        if array[middle_index] == item:
            return middle_index
        elif array[middle_index] < item:
            lower_index = middle_index + 1
        elif array[middle_index] > item:
            upper_index = middle_index - 1

    # Did not find
    return None

def binary_search(array, item):
    """return the index of item in sorted array or None if item is not found"""
    # change this to call your implementation to verify it passes all tests
    return binary_search_iterative(array, item)

link to my linear search code: https://gist.github.com/anonymous/be81dc4ab1a26328785ed8cffce33346

def linear_search(array, item):
    for index, value in enumerate(array):
        if item == value:
            return index  # found
    return None  # not found

---

#!python

from search import linear_search, binary_search
import unittest


class SearchTest(unittest.TestCase):

    def test_binary_search_with_items_in_list(self):
        # binary search requires list values to be in sorted order
        names = ['Alex', 'James', 'Julia', 'Matthew', 'Nathan', 'Conrad', 'John']
        # binary search should return the index of each item in the list
        assert binary_search(names, 'Alex') == 0
        assert binary_search(names, 'James') == 1
        assert binary_search(names, 'Julia') == 2
        assert binary_search(names, 'Matthew') == 3
        assert binary_search(names, 'Nathan') == 4
        assert binary_search(names, 'Conrad') == 5
        assert binary_search(names, 'John') == 6

    def test_binary_search_with_items_in_list2(self):
        # binary search requires list values to be in sorted order
        names = ['Person0', 'Person1', 'Person2', 'Person3', 'Person4', 'Person5', 'Person6']
        # binary search should return the index of each item in the list
        assert linear_search(names, 'Person0') == 0
        assert linear_search(names, 'Person1') == 1
        assert linear_search(names, 'Person2') == 2
        assert linear_search(names, 'Person3') == 3
        assert linear_search(names, 'Person4') == 4
        assert linear_search(names, 'Person5') == 5
        assert linear_search(names, 'Person6') == 6

    def test_binary_search_with_items_not_in_list(self):
        # binary search requires list values to be in sorted order
        names = ['Alex', 'James', 'Julia', 'Matthew', 'Nathan', 'Conrad', 'John']
        # binary search should return None for any item not in the list
        assert binary_search(names, 'Jeffrey') is None
        assert binary_search(names, 'nobody') is None

    def test_binary_search_with_items_not_in_list2(self):
        # binary search requires list values to be in sorted order
        names = ['Person5', 'Person2', 'Person4', 'Person1', 'Person3', 'Person6', 'Person0']
        # binary search should return None for any item not in the list
        assert binary_search(names, 'Jack-in-Box') is None
        assert binary_search(names, 'nobody') is None


if __name__ == '__main__':
    unittest.main()

Answer 1

Be sure to check bisect the Python's standard binary search module.

This is a good implementation of Binary Search; I just have a few nitpicks:

• How about a high and low overload?

  Instead of declaring your lower and higher index like this:

  lower_index = 0
  upper_index = len(array) - 1
  

  You could give them as argument overloads

  def binary_search_iterative(array, item, low=0, high=None):
      if high is None:
          high = len(array)
      ...
  

• Change your comments accordingly

  Don't mix comments and docstrings, stick with docstrings if you want to explain arguments

  """iteratively return the index of the item with binary search or None if not found"""
  # Sorted array that has to be the condition
  # go through several iteration until we found this
  # First, set the lower_index = 0
  # upper_index as the length of array -1
  lower_index = 0
  

  That could be this:

  """Return the index of the item with binary search or None if not found
  
  Keyword arguments:
  array -- the list to search in
  item -- the item to search for
  high -- the highest index to search in between (default highest index of the array)
  low -- the lowest index to search in between (default 0)
  """
  

  This uses the PEP257 Docstring style, but you may use your own as long as it is clear.

• Remove redundant comment

  Commenting is good, but don't overdo it; your code is good enough to speak for itself. These comments feel redundant:

  # calculate the middle index by sum the lower_index and upper_index and divide by 2
  # check if the item is found
  # Did not find