# iterative binary_search Python implementation

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


#!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, '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()

• just fixed the unit-testing by importing both binary_search and linear_search to unit-test Dec 5, 2017 at 19:25

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)
...


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