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:
    vector searchRange(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;
}