cs207labs/binsearch.py at master · akhilketkar/cs207labs · 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
121
122
123
124
125
126
127
128
129
def binary_search(da_array: list, needle, left:int=0, right:int=-1) -> int:
    """
    An algorithm that operates in O(lg(n)) to search for an element
    in an array sorted in ascending order.

    Parameters
    ----------
    da_array : list
        a list of "comparable"items sorted in non-descending order
    needle: an item to find in the array; it may or may not
        be in the array
    left: int, optional
        the left index in the array to search from. Default 0
    right: int, optional
        the right index in the array to search to. Default is -1
        in which case we will use the end of the array `len(da_array) - 1`

    Returns
    -------
    index: int
        an integer representing the index of `needle` if found, and -1
        otherwise

    Notes
    -----
    PRE: `da_array` is sorted in non-decreasing order (thus items in
        `da_array` must be comparable: implement < and ==)
    POST:
        - `da_array` is not changed by this function (immutable)
        - returns `index`=-1 if `needle` is not in `da_array`
        - returns an int `index ` in [0:len(da_array)] if
          `index` is in `da_array`
    INVARIANTS:
        - If `needle` in `da_array`, needle in `da_array[rangemin:rangemax]`
          is a loop invariant in the while loop below.

    Examples
    --------
    >>> input = list(range(10))
    >>> binary_search(input, 5)
    5
    >>> binary_search(input, 4.5)
    -1
    >>> binary_search(input, 10)
    -1
    >>> binary_search([5], 5)
    0
    >>> binary_search([5], 4)
    -1
    >>> import numpy as np
    >>> binary_search([1,2,np.inf], 2)
    1
    >>> binary_search([1,2,np.inf], np.inf)
    2
    >>> binary_search(input, 5, 1,3)
    -1
    >>> binary_search(input, 2, 1,3)
    2
    >>> binary_search(input, 2, 3, 1)
    -1
    >>> binary_search(input, 2, 2, 2)
    2
    >>> binary_search(input, 5, 2, 2)
    -1
    """


    if left==0:
        rangemin = 0
    else:
        rangemin = left
    if right==-1:
        rangemax=len(da_array) - 1
    else:
        rangemax=right
    while True:
        "needle in da_array => needle in da_array[rangemin:rangemax]"
        if rangemin > rangemax:
            index = -1
            return index
        #If rangemin and rangemax are both very high we do not want overflow,
        #so get the midpoint like this:
        midpoint = rangemin + (rangemax - rangemin)//2
        if da_array[midpoint] > needle:#lower part
            rangemax = midpoint - 1
        elif da_array[midpoint] < needle:
            rangemin = midpoint + 1
        else:
            index = midpoint
            return index

############ TESTING ################
import unittest
class TestBinSearch(unittest.TestCase):
    def test_checkPresent(self):
        inp = range(10)
        self.assertEqual(binary_search(inp,5),5)

    def test_checkAbsent(self):
        inp = range(10)
        self.assertEqual(binary_search(inp,-10),-1)

    def test_checkLarge1(self):
        'left edge'
        inp = range(10000)
        self.assertEqual(binary_search(inp,0),inp.index(0))

    def test_checkLarge2(self):
        'right edge'
        inp = range(10000)
        self.assertEqual(binary_search(inp,9999),inp.index(9999))

    def test_badInput1(self):
        """ The array must consist of things that can be compared to the needle """
        inp = ['a',1,2,3,4,'g']
        with self.assertRaises(TypeError):
            binary_search(inp,'g')

    def test_badInput2(self):
        """ The first argument must be a list or something that can be interpreted as a list """
        with self.assertRaises(TypeError):
            binary_search(5,5)

    def test_strings(self):
        inp = 'abcdefghi'
        self.assertEqual(binary_search(inp,'c'),2)

    def test_empty(self):
        self.assertEqual(binary_search([],9999),-1)