-
Notifications
You must be signed in to change notification settings - Fork 17
/
binary-search.py
88 lines (61 loc) · 2.23 KB
/
binary-search.py
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
import unittest
class Solution:
def search(self, nums, target):
left, right = 0, len(nums)
while left < right:
middle = left + (right - left) // 2
if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle
else:
return middle
return -1
def search1(self, nums, target):
if not len(nums):
return -1
left, right = 0, len(nums) - 1
if nums[left] == target:
return left
if nums[right] == target:
return right
if nums[left] > target:
return -1
if nums[right] < target:
return -1
while right - left > 1:
center = int((right + left) / 2)
if nums[center] < target:
left = center
elif nums[center] > target:
right = center
else:
return center
return -1
class TestSolution(unittest.TestCase):
def setUp(self):
self.sol = Solution()
def test_empty(self):
self.assertEqual(self.sol.search([], 123), -1)
def test_one_non_matching(self):
self.assertEqual(self.sol.search([0], 123), -1)
def test_one_matching(self):
self.assertEqual(self.sol.search([123], 123), 0)
def test_out_of_boundaries_left(self):
self.assertEqual(self.sol.search([5, 6, 7, 8, 9, 10], 2), -1)
def test_out_of_boundaries_right(self):
self.assertEqual(self.sol.search([5, 6, 7, 8, 9, 10], 123), -1)
def test_not_in_array(self):
self.assertEqual(self.sol.search([5, 6, 7, 9, 10], 8), -1)
def test_leftmost_match(self):
self.assertEqual(self.sol.search([5, 6, 7, 9, 10], 5), 0)
def test_rightmost_match(self):
self.assertEqual(self.sol.search([5, 6, 7, 9, 10], 10), 4)
def test_central_match(self):
self.assertEqual(self.sol.search([5, 6, 7, 9, 10], 7), 2)
def test_match_custom1(self):
self.assertEqual(self.sol.search([5, 6, 7, 9, 10], 6), 1)
def test_match_custom2(self):
self.assertEqual(self.sol.search([5, 6, 7, 9, 10], 9), 3)
if __name__ == "__main__":
unittest.main()