find_first_and_last_position_of_element_in_sorted_array
1# @leet start 2class Solution: 3 def searchRange(self, nums: list[int], target: int) -> list[int]: 4 """ 5 This question asks us to find the first and last position of an element 6 in a sorted array. 7 To do this, we can bisect left and bisect right using binary search, finding 8 the lowest and highest values where the value is the target. 9 10 On the bisect left side, if we find the current value is equal to target, 11 we set r = mid - 1 and continue the iteration. 12 13 On the bisect right side, if we find the current value is equal to target, 14 we set l = mid + 1 and continue the iteration. 15 16 One thing to note is that if the value isn't found, we have to return 17 [-1, -1], so for both functions, we can have a sentinel value, found, 18 which we can return, denoting if we've found the target. 19 We can use this to find out if we found the value or not. 20 """ 21 n = len(nums) 22 23 def left_side(l, r): 24 found = False 25 while l <= r: 26 mid = (l + r) // 2 27 if nums[mid] == target: 28 found = True 29 r = mid - 1 30 elif nums[mid] > target: 31 r = mid - 1 32 else: 33 l = mid + 1 34 return (found, l) 35 36 def right_side(l, r): 37 found = False 38 while l <= r: 39 mid = (l + r) // 2 40 if nums[mid] == target: 41 found = True 42 l = mid + 1 43 elif nums[mid] > target: 44 r = mid - 1 45 else: 46 l = mid + 1 47 return (found, r) 48 49 ((found_left, l), (found_right, r)) = left_side(0, n - 1), right_side(0, n - 1) 50 if not found_left or not found_right: 51 return [-1, -1] 52 return [l, r] 53 54 55# @leet end 56 57 58def test(): 59 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def searchRange(self, nums: list[int], target: int) -> list[int]: 5 """ 6 This question asks us to find the first and last position of an element 7 in a sorted array. 8 To do this, we can bisect left and bisect right using binary search, finding 9 the lowest and highest values where the value is the target. 10 11 On the bisect left side, if we find the current value is equal to target, 12 we set r = mid - 1 and continue the iteration. 13 14 On the bisect right side, if we find the current value is equal to target, 15 we set l = mid + 1 and continue the iteration. 16 17 One thing to note is that if the value isn't found, we have to return 18 [-1, -1], so for both functions, we can have a sentinel value, found, 19 which we can return, denoting if we've found the target. 20 We can use this to find out if we found the value or not. 21 """ 22 n = len(nums) 23 24 def left_side(l, r): 25 found = False 26 while l <= r: 27 mid = (l + r) // 2 28 if nums[mid] == target: 29 found = True 30 r = mid - 1 31 elif nums[mid] > target: 32 r = mid - 1 33 else: 34 l = mid + 1 35 return (found, l) 36 37 def right_side(l, r): 38 found = False 39 while l <= r: 40 mid = (l + r) // 2 41 if nums[mid] == target: 42 found = True 43 l = mid + 1 44 elif nums[mid] > target: 45 r = mid - 1 46 else: 47 l = mid + 1 48 return (found, r) 49 50 ((found_left, l), (found_right, r)) = left_side(0, n - 1), right_side(0, n - 1) 51 if not found_left or not found_right: 52 return [-1, -1] 53 return [l, r]
def
searchRange(self, nums: list[int], target: int) -> list[int]:
4 def searchRange(self, nums: list[int], target: int) -> list[int]: 5 """ 6 This question asks us to find the first and last position of an element 7 in a sorted array. 8 To do this, we can bisect left and bisect right using binary search, finding 9 the lowest and highest values where the value is the target. 10 11 On the bisect left side, if we find the current value is equal to target, 12 we set r = mid - 1 and continue the iteration. 13 14 On the bisect right side, if we find the current value is equal to target, 15 we set l = mid + 1 and continue the iteration. 16 17 One thing to note is that if the value isn't found, we have to return 18 [-1, -1], so for both functions, we can have a sentinel value, found, 19 which we can return, denoting if we've found the target. 20 We can use this to find out if we found the value or not. 21 """ 22 n = len(nums) 23 24 def left_side(l, r): 25 found = False 26 while l <= r: 27 mid = (l + r) // 2 28 if nums[mid] == target: 29 found = True 30 r = mid - 1 31 elif nums[mid] > target: 32 r = mid - 1 33 else: 34 l = mid + 1 35 return (found, l) 36 37 def right_side(l, r): 38 found = False 39 while l <= r: 40 mid = (l + r) // 2 41 if nums[mid] == target: 42 found = True 43 l = mid + 1 44 elif nums[mid] > target: 45 r = mid - 1 46 else: 47 l = mid + 1 48 return (found, r) 49 50 ((found_left, l), (found_right, r)) = left_side(0, n - 1), right_side(0, n - 1) 51 if not found_left or not found_right: 52 return [-1, -1] 53 return [l, r]
This question asks us to find the first and last position of an element in a sorted array. To do this, we can bisect left and bisect right using binary search, finding the lowest and highest values where the value is the target.
On the bisect left side, if we find the current value is equal to target, we set r = mid - 1 and continue the iteration.
On the bisect right side, if we find the current value is equal to target, we set l = mid + 1 and continue the iteration.
One thing to note is that if the value isn't found, we have to return [-1, -1], so for both functions, we can have a sentinel value, found, which we can return, denoting if we've found the target. We can use this to find out if we found the value or not.
def
test():