Certainly! Let's discuss both approaches for the problem "Find First and Last Position of Element in Sorted Array" on LeetCode.
Problem Description:
Given a sorted array of integers and a target value, return the starting and ending position of a given target value in the array, or -1 if the target is not found.
Approach 1: Using Linear Search
In this approach, we can perform a linear search through the array to find the first and last occurrence of the target value.
def searchRange_linear(nums, target):
start, end = -1, -1
for i in range(len(nums)):
if nums[i] == target:
if start == -1:
start = i
end = i
return [start, end]
Approach 2: Using Modified Binary Search (Optimal)
This approach involves performing binary search twice to find the first and last occurrence of the target value separately. We can use a modified binary search to find the first occurrence and then another modified binary search to find the last occurrence.
def searchRange_binary(nums, target):
def find_first_occurrence(nums, target):
start, end = 0, len(nums) - 1
first_occurrence = -1
while start <= end:
mid = start + (end - start) // 2
if nums[mid] >= target:
end = mid - 1
if nums[mid] == target:
first_occurrence = mid
else:
start = mid + 1
return first_occurrence
def find_last_occurrence(nums, target):
start, end = 0, len(nums) - 1
last_occurrence = -1
while start <= end:
mid = start + (end - start) // 2
if nums[mid] <= target:
start = mid + 1
if nums[mid] == target:
last_occurrence = mid
else:
end = mid - 1
return last_occurrence
first = find_first_occurrence(nums, target)
last = find_last_occurrence(nums, target)
return [first, last]
The second approach is more efficient as it uses binary search, which has a time complexity of O(log n) for each search, where n is the number of elements in the array. Therefore, the overall time complexity of the second approach is O(log n).
