Searchfora Range Algorithm
The Search for a Range Algorithm, also known as the Find First and Last Position of Element in Sorted Array Algorithm, is a binary search-based algorithm designed to find the starting and ending positions of a given target value in a sorted array. It efficiently locates a specific element in the array and returns its range, i.e., the first and last occurrence of the element within the array. The algorithm is particularly useful when dealing with large, sorted datasets where a linear search would be highly inefficient. By leveraging the binary search technique, the Search for a Range Algorithm can solve the problem with a time complexity of O(log n).
The algorithm works by first identifying the middle element of the sorted array and comparing it to the target value. If the target is less than the middle element, the search continues in the left half; if the target is greater, the search moves to the right half. This process is repeated until the target value is found or the search space becomes empty. Once the target is located, the algorithm proceeds to search for the first and last occurrences of the target value in the array. This is achieved by applying a slightly modified binary search to find the first occurrence, followed by another modified search to locate the last occurrence. The range of the target value is then returned as a pair of indices, indicating its starting and ending positions within the sorted array.
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> range;
range.push_back(find_lower_bound(A, n, target));
range.push_back(find_upper_bound(A, n, target));
return range;
}
int find_lower_bound(int A[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] >= target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
if (A[left] == target)
return left;
return -1;
}
int find_upper_bound(int A[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] <= target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
if (A[right] == target)
return right;
return -1;
}
};
