binary search


See On Github

Data

Contributor

Generic placeholder thumbnail

by rohanp

in python

Source Code

#!/usr/bin/env python3
""" Binary Search """
__author__ = "Rohan Pandit"

def binary_search(lst, el):
	#returns index of element, or -1 if not in lst
	return binary_search_recur(lst, el, 0, len(lst))

def binary_search_recur(lst, el, min_idx, max_idx):
	middle_idx = (max_idx - min_idx) // 2 + min_idx

	if min_idx == max_idx:
		return -1
	elif el == lst[ middle_idx ]:
		return middle_idx
	elif max_idx - min_idx == 1:
		return -1
	elif lst[ middle_idx ] < el:
		return binary_search_recur(lst, el, middle_idx, max_idx)
	else:
		return binary_search_recur(lst, el, min_idx, middle_idx)
import unittest
from binary_search import binary_search


class BinarySearchTest(unittest.TestCase):
    def test_empty(self):
        arr = []
        self.assertEquals(binary_search(arr, 1), -1)

    def test_single(self):
        arr = [1]
        self.assertEquals(binary_search(arr, 1), 0)

    def test_length_of_two(self):
        arr = [0, 1]
        self.assertEquals(binary_search(arr, 1), 1)
        self.assertEquals(binary_search(arr, 0), 0)

    def test_basic(self):
        arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        for i, n in enumerate(arr):
            self.assertEquals(binary_search(arr, n), i)

    def test_odd_len(self):
        arr = [2, 4, 6, 7, 9, 10, 14, 16, 19]
        for i, n in enumerate(arr):
            self.assertEquals(binary_search(arr, n), i)

    def test_missing(self):
        arr = [2, 4, 6, 7, 9, 10, 14, 16, 19]
        self.assertEquals(binary_search(arr, 5), -1)


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