binary search


See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

in python

Source Code

# Expects the array to be sorted
def binary_search(arr, target):
    if len(arr) < 1:
        return -1

    middle = int(len(arr) / 2)
    middle_value = arr[middle]

    if middle_value > target:
        return binary_search(arr[:middle], target)
    elif middle_value < target:
        v = binary_search(arr[middle + 1:], target)
        # since we're jumping forward in the slice (arr[middle+1:])
        # we need to compensate that by adding the jump size
        if v < 0:
            return v
        else:
            return middle + v + 1

    return middle
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_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()