m3w3

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