algorithms/test_binary_search.py at master · RodriguezLucha/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#!/usr/bin/env python

class Solution(object):

    def search(self, A, t):
        l = 0
        r = len(A) - 1

        while True:
            if r < l:
                return -1

            m = (l + r) / 2
            val = A[m]

            if t > val:
                l = m + 1
            if t < val:
                r = m - 1
            if t == val:
                return m


def test_basic_found():
    s = Solution()
    A = [-1, 0, 3, 5, 9, 12]
    target = 9
    expected = 4
    actual = s.search(A, target)
    assert actual == expected


def test_basic_not_found():
    s = Solution()
    A = [-1, 0, 3, 5, 9, 12]
    target = 9
    expected = 4
    actual = s.search(A, target)
    assert actual == expected


def test_basic_one_found():
    s = Solution()
    A = [1]
    target = 1
    expected = 0
    actual = s.search(A, target)
    assert actual == expected


def test_basic_none():
    s = Solution()
    A = []
    target = 1
    expected = -1
    actual = s.search(A, target)
    assert actual == expected


def test_basic_odd():
    s = Solution()
    A = [1, 2, 3]
    target = 2
    expected = 1
    actual = s.search(A, target)
    assert actual == expected


def test_basic_even_left():
    s = Solution()
    A = [1, 2, 3, 4]
    target = 3
    expected = 2
    actual = s.search(A, target)
    assert actual == expected


def test_basic_even_right():
    s = Solution()
    A = [1, 2, 3, 4]
    target = 2
    expected = 1
    actual = s.search(A, target)
    assert actual == expected


def test_basic_even_edge_left():
    s = Solution()
    A = [1, 2, 3, 4]
    target = 1
    expected = 0
    actual = s.search(A, target)
    assert actual == expected


def test_two_right():
    s = Solution()
    A = [1, 2]
    target = 2
    expected = 1
    actual = s.search(A, target)
    assert actual == expected


def test_two_left():
    s = Solution()
    A = [1, 2]
    target = 1
    expected = 0
    actual = s.search(A, target)
    assert actual == expected


def test_basic_even_edge_right():
    s = Solution()
    A = [1, 2, 3, 4]
    target = 4
    expected = 3
    actual = s.search(A, target)
    assert actual == expected