Find First and Last Position of Element in Sorted Array
This article was translated by AI (LLM). There may be errors or inaccuracies. For the original content, please refer to the original version.
Problem URL: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Essentially a binary search problem, searching for the start and end positions
Solution Approaches
Recursive Method
Code
def check_nums_middle(target: int, nums: list, start_position: int, stop_position: int):
if start_position == stop_position:
if target == nums[start_position]:
return start_position, stop_position
else:
return [-1, -1]
elif start_position + 1 == stop_position:
r_start_position = -1
r_stop_position = -1
if nums[start_position] == target:
r_start_position = start_position
r_stop_position = start_position
if nums[stop_position] == target:
if r_start_position == -1:
r_start_position = stop_position
r_stop_position = stop_position
return r_start_position, r_stop_position
else:
middle_position = int((start_position + stop_position) / 2)
middle_position_num = nums[middle_position]
if target > middle_position_num:
return check_nums_middle(target, nums, middle_position, stop_position)
elif target < middle_position_num:
return check_nums_middle(target, nums, start_position, middle_position)
else: # Middle value equals target
left_position_range, left_r = check_nums_middle(
target, nums, start_position, middle_position)
right_l, right_position_range = check_nums_middle(
target, nums, middle_position + 1, stop_position)
if left_r == -1:
return right_l, right_position_range
elif right_l == -1:
return left_position_range, left_r
else:
return left_position_range, right_position_range
def main(target: int, nums: list) -> list:
if len(nums) == 0:
return [-1, -1]
left_position_range, right_position_range = check_nums_middle(
target, nums, 0, len(nums) - 1)
return [left_position_range, right_position_range]LeetCode Test
Iterative Approach
When the list is sufficiently long, recursion may cause tail call issues, while iteration avoids this
Code
def for_num_check(target: int, nums: list) -> list:
start_position = 0
stop_position = len(nums) - 1
# Find middle value equal to target
while True:
middle_position = int((start_position + stop_position) / 2)
#print(f"find target: {start_position}, {stop_position}")
middle_position_num = nums[middle_position]
if target == middle_position_num:
break
# Number doesn't exist
elif stop_position - start_position <= 1:
if target == nums[stop_position]:
middle_position = stop_position
break
else:
return [-1, -1]
elif target > middle_position_num:
start_position = middle_position + 1
else:
stop_position = middle_position - 1
# Determine left and right ranges
left_start_position = start_position
left_stop_position = middle_position - 1
#print(f"target {middle_position}")
#print(f"left: {left_start_position}, {left_stop_position}")
if left_start_position <= left_stop_position:
left_position = left_num_check(target, nums, left_start_position,
left_stop_position)
if left_position == -1:
left_position = middle_position
else:
left_position = middle_position
#print(f"left: {left_position}")
right_start_position = middle_position + 1
right_stop_position = stop_position
#print(f"right: {right_start_position}, {right_stop_position}")
if right_start_position <= right_stop_position:
right_position = right_num_check(target, nums, right_start_position,
right_stop_position)
if right_position == -1:
right_position = middle_position
else:
right_position = middle_position
#print(f"right: {right_position}")
return [left_position, right_position]
# Find leftmost target value
def left_num_check(target: int, nums: list, start_position: int,
stop_position: int) -> int:
if nums[stop_position] != target:
return -1
while True:
middle_position = int((start_position + stop_position) / 2)
middle_position_num = nums[middle_position]
if middle_position == start_position:
if target == middle_position_num:
return middle_position
else:
return stop_position
elif target == middle_position_num and\
target > nums[middle_position - 1]:
return middle_position
elif target == middle_position_num:
stop_position = middle_position - 1
else:
start_position = middle_position + 1
# Find rightmost target value
def right_num_check(target: int, nums: list, start_position: int,
stop_position: int) -> int:
if nums[start_position] != target:
return -1
while True:
middle_position = int((start_position + stop_position) / 2)
middle_position_num = nums[middle_position]
if middle_position == stop_position:
if target == middle_position_num:
return middle_position
else:
return start_position
elif target == middle_position_num and\
target < nums[middle_position + 1]:
return middle_position
elif target == middle_position_num:
start_position = middle_position + 1
else:
stop_position = middle_position - 1
def main(target: int, nums: list) -> list:
if len(nums) == 0:
return [-1, -1]
return for_num_check(target, nums)LeetCode Test
Testing Method
print(main(0, [0, 0, 0, 0, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 8, 9, 9, 10, 10, 11, 11]))Summary
Iteration has some advantages (like avoiding tail calls) over recursion, but it’s more complex to write and prone to errors. In practical applications (when not writing general-purpose libraries), it’s not recommended 🙁