gistfile1.txt

from unittest import TestCase, main


def bin_s(search_space, thing):
    low = 0
    high = len(search_space) - 1
    while low + 1 < high:
        # this is python 2, so will round down
        mid = (high - low) / 2 + low

        for i in high, low, mid:
            if search_space[i] == thing:
                return i

        if search_space[high] < thing or search_space[low] > thing:
            return -1

        at_mid = search_space[mid]
        if at_mid < thing:
            # search in top half
            low = mid
        if at_mid > thing:
            # search in bottom half
            high = mid

    return -1


class TestBinS(TestCase):
    def setUp(self):
        self.search_space = [1, 4, 7, 9, 12, 13, 14, 15, 15, 15, 21]

    def test_not_found(self):
        self.assertEqual(-1, bin_s(self.search_space, 20))

    def test_found_in_middle(self):
        self.assertEqual(5, bin_s(self.search_space, 13))

    def test_found_in_fist_space(self):
        self.assertEqual(0, bin_s(self.search_space, 1))

    def test_found_in_last_space(self):
        last_place = len(self.search_space) - 1
        thing_at_last_place = self.search_space[-1]
        self.assertEqual(
            last_place, bin_s(self.search_space, thing_at_last_place))

    def test_found_if_multiple_copies(self):
        location = bin_s(self.search_space, 15)
        self.assertIn(location, [7, 8, 9])

    def test_found_in_first_of_two_middle(self):
        self.search_space.append(27)
        location = bin_s(self.search_space, 13)
        self.assertEqual(location, 5)

    def test_found_in_second_of_two_middle(self):
        self.search_space.append(27)
        location = bin_s(self.search_space, 14)
        self.assertEqual(location, 6)

    def test_not_found_in_empty(self):
        self.search_space = []
        location = bin_s(self.search_space, 14)
        self.assertEqual(location, -1)

    def test_found_in_search_space_all_the_same(self):
        self.search_space = [1, 1, 1, 1, 1, 1]
        location = bin_s(self.search_space, 1)
        self.assertIn(location, [0, 1, 2, 3, 4, 5])


if __name__ == "__main__":
    main()