C++ and Dart Solutions for Finding the First and Last Position of an Element in a Sorted Array

C++ and Dart Solutions for Finding the First and Last Position of an Element in a Sorted Array

This code presents efficient solutions in C++ and Dart to determine the first and last positions of a target element within a sorted array. The implementations utilize binary search algorithms for optimal performance.

C++ Solution:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin(),right = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
        if (left < nums.size() && nums[left] == target) return {left, right};
        return {-1, -1};
    }
};

Dart Solution:

class Solution {
  List searchRange(List<int> nums, int target) {
    if (nums.isEmpty) return [-1, -1];
    int left = lowerBound(nums, target), right = upperBound(nums, target) - 1;
    if (left < nums.length && nums[left] == target) return [left, right];
    return [-1, -1];
  }
  
  int lowerBound(List<int> nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
      int mid = (left + right) ~/ 2;
      if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    return left;
  }
  
  int upperBound(List<int> nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
      int mid = (left + right) ~/ 2;
      if (nums[mid] <= target) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    return left;
  }
}

Explanation:

Both solutions leverage the lower_bound and upper_bound functions (or their equivalents in Dart) to efficiently find the first and last occurrences of the target element within the sorted array. The core logic involves:

1. Handling Empty Array: The code checks for an empty array and returns [-1, -1] if the array is empty.
2. Binary Search: The lower_bound and upper_bound functions perform binary search to determine the lower and upper bounds of the target element. In Dart, custom lowerBound and upperBound functions are provided to achieve the same functionality.
3. Validating Results: If the found lower bound is within the array bounds and the corresponding element matches the target, the code returns the lower and upper bounds as the result. Otherwise, [-1, -1] is returned to indicate the element's absence.

This approach combines the power of binary search with clear and concise code for finding the first and last occurrences of an element within a sorted array, ensuring optimal performance and readability.