# Binary_Search

Oct 16th, 2020 (edited)
2,371
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from typing import *
2.
3. def bs(nums: List[int], target: int) -> int:
4.     """
5.    Return the index at which target appears in nums.
6.    If there are multiple targets in nums, return first instance found during a binary search.
7.
8.    Return -1 if target doesn't exist in nums.
9.    """
10.     n = len(nums)
11.     # base cases:
12.     # nums = [0, 1], target = 2, mid_i = 1
13.     # nums = [0], target = 2, mid_i = 0
14.     if n == 0:
15.         return -1
16.     elif n == 1:
17.         return 0 if nums[0] == target else -1
18.     elif n == 2:
19.         if nums[1] == target:
20.             return 1
21.         else:
22.             return 0 if nums[0] == target else -1
23.
24.     # recursive step: anything length with n > 2
25.     mid_i = n // 2
26.     mid = nums[mid_i]
27.     if mid < target:
28.         # search right
29.         search_right =  bs(nums[mid_i + 1:], target)
30.         return mid_i + 1 + search_right if search_right != -1 else -1
31.     elif target < mid:
32.         search_left = bs(nums[:mid_i], target)
33.         return search_left if search_left != -1 else -1
34.     else:
35.         return mid_i
36.
37. if __name__ == "__main__":
38.     nums, target = [1, 1, 1, 1, 1, 1, 1, 1], 1
39.     print(bs(nums, target))
40.     nums, target = [0, 1, 2, 3, 3, 3, 3, 3, 3, 4, 5, 6, 7], 3
41.     print(bs(nums, target))
42.     nums, target = [0, 1, 2, 3, 4, 5], 10
43.     print(bs(nums, target))
44.     nums, target = [0, 1, 2, 2, 2, 2, 2, 2, 3, 4, 5], 2
45.     print(bs(nums, target))
46.     nums, target = [0, 1, 2], 1
47.     print(bs(nums, target))
48.     nums, target = [0, 1], 2
49.     print(bs(nums, target))
RAW Paste Data