Solution For Find First And Last Position Of Element In Sorted Array
Problem statement: Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value in the array. If the target is not found in the array, return [-1, -1].
Solution:
Approach 1: Linear Scan
The most intuitive solution to this problem is to simply iterate over the entire array and find the first index of the target, and then continue iterating until we find the last index. This solution has a time complexity of O(n), where n is the length of the array.
Code:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
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: Binary Search
Since the array is sorted, we can use the Binary Search algorithm to find the first and last occurrence of the target value. First, we perform a regular Binary Search to find the first occurrence of the target, and then search for the last occurrence by performing another Binary Search in the right half of the array. This approach has a time complexity of O(log n), where n is the length of the array.
Code:
“`
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums,target,lower):
left = 0
right = len(nums)-1
result = -1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
result = mid
if lower:
right = mid – 1
else:
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid – 1
return result
first = binarySearch(nums,target,True)
if first == -1:
return [-1,-1]
last = binarySearch(nums,target,False)
return [first,last]
“`
Time Complexity: O(log n) – Binary Search Algorithm
Space Complexity: O(1) – Constant Space Required
Test Cases:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Step by Step Implementation For Find First And Last Position Of Element In Sorted Array
class Solution { public int[] searchRange(int[] nums, int target) { // Base case if (nums.length == 0) { return new int[] {-1, -1}; } // Binary search for the leftmost element int left = 0; int right = nums.length - 1; int leftmost = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { // Check if this is the leftmost element if (mid == 0 || nums[mid - 1] != target) { leftmost = mid; break; } else { right = mid - 1; } } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } // Binary search for the rightmost element left = 0; right = nums.length - 1; int rightmost = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { // Check if this is the rightmost element if (mid == nums.length - 1 || nums[mid + 1] != target) { rightmost = mid; break; } else { left = mid + 1; } } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return new int[] {leftmost, rightmost}; } }
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # return the first and last indices of an element in a sorted array # check for empty array if not nums: return [-1, -1] # search for the left index left = 0 right = len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 else: right = mid # if the target is not found, return [-1, -1] if nums[left] != target: return [-1, -1] # search for the right index right = len(nums) - 1 while left < right: mid = (left + right) // 2 + 1 if nums[mid] > target: right = mid - 1 else: left = mid return [left, right]
var searchRange = function(nums, target) { //create a variable to store the first position of the target //create a variable to store the last position of the target //iterate through the array //if the current element is equal to the target //if the first position is null //set the first position to the current index //set the last position to the current index //if the current element is greater than the target //break out of the loop //return an array with the first and last position };
class Solution { public: vectorsearchRange(vector & nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { int l = mid, r = mid; while (l > 0 && nums[l - 1] == target) --l; while (r < nums.size() - 1 && nums[r + 1] == target) ++r; return {l, r}; } else if (nums[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return {-1, -1}; } };
public int[] SearchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = FindFirst(nums, target); result[1] = FindLast(nums, target); return result; } private int FindFirst(int[] nums, int target) { int index = Array.BinarySearch(nums, target); if (index < 0) return -1; while (index > 0 && nums[index - 1] == target) index--; return index; } private int FindLast(int[] nums, int target) { int index = Array.BinarySearch(nums, target); if (index < 0) return -1; while (index < nums.Length - 1 && nums[index + 1] == target) index++; return index; }