def searchRange(nums, target):
def findFirst(nums, target):
left, right = 0, len(nums) - 1
index = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
if nums[mid] == target:
index = mid
return index
def findLast(nums, target):
left, right = 0, len(nums) - 1
index = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
if nums[mid] == target:
index = mid
return index
return [findFirst(nums, target), findLast(nums, target)]
nums = [5, 7, 7, 8, 8, 10]
target = 8
print(searchRange(nums, target))
Explanation (Python):
The Python solution utilizes two helper functions, findFirst and findLast, to find the first and last occurrences of the target element in the sorted array.
The findFirst function uses a modified binary search to find the leftmost occurrence of the target element.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Iterate until left becomes greater than right.
Find the middle element using (left + right) // 2.
If the middle element is greater than or equal to the target, update the right pointer to mid - 1 to search the left half.
If the middle element is equal to the target, update the index variable with the current index and continue searching in the left half.
If the middle element is less than the target, update the left pointer to mid + 1 to search the right half.
Return the index variable as the leftmost occurrence of the target element.
The findLast function follows a similar logic but searches for the rightmost occurrence of the target element.
Finally, the main function returns a list containing the results of findFirst and findLast functions.
class Solution {
public int[] searchRange(int[] nums, int target) {
int first = findFirst(nums, target);
int last = findLast(nums, target);
return new int[] {first, last};
}
private int findFirst(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
if (nums[mid] == target) {
index = mid;
}
}
return index;
}
private int findLast(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
if (nums[mid] == target) {
index = mid;
}
}
return index;
}
public static void main(String[] args) {
int[] nums = {5, 7, 7, 8, 8, 10};
int target = 8;
Solution solution = new Solution();
int[] result = solution.searchRange(nums, target);
for (int num : result) {
System.out.print(num + " ");
}
}
}
Explanation (Java):
The Java solution follows a similar approach to the Python solution, utilizing two helper methods, findFirst and findLast, to find the first and last occurrences of the target element in the sorted array.
The findFirst method uses a modified binary search to find the leftmost occurrence of the target element.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Perform the binary search until left becomes greater than right.
Find the middle element using left + (right - left) / 2.
If the middle element is greater than or equal to the target, update the right pointer to mid - 1 to search the left half.
If the middle element is equal to the target, update the index variable with the current index and continue searching in the left half.
If the middle element is less than the target, update the left pointer to mid + 1 to search the right half.
Return the index variable as the leftmost occurrence of the target element.
The findLast method follows a similar logic but searches for the rightmost occurrence of the target element.
Finally, the searchRange method combines the results of findFirst and findLast methods into an integer array and returns it.
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector searchRange(vector& nums, int target) {
int first = findFirst(nums, target);
int last = findLast(nums, target);
return {first, last};
}
private:
int findFirst(vector& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
if (nums[mid] == target) {
index = mid;
}
}
return index;
}
int findLast(vector& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
if (nums[mid] == target) {
index = mid;
}
}
return index;
}
};
int main() {
vector nums = {5, 7, 7, 8, 8, 10};
int target = 8;
Solution solution;
vector result = solution.searchRange(nums, target);
for (int num : result) {
cout << num << " ";
}
return 0;
}
Explanation (C++):
The C++ solution follows a similar approach to the Python and Java solutions, using two private member functions, findFirst and findLast, to find the first and last occurrences of the target element in the sorted array.
The findFirst function uses a modified binary search to find the leftmost occurrence of the target element.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Perform the binary search until left becomes greater than right.
Find the middle element using left + (right - left) / 2.
If the middle element is greater than or equal to the target, update the right pointer to mid - 1 to search the left half.
If the middle element is equal to the target, update the index variable with the current index and continue searching in the left half.
If the middle element is less than the target, update the left pointer to mid + 1 to search the right half.
Return the index variable as the leftmost occurrence of the target element.
The findLast function follows a similar logic but searches for the rightmost occurrence of the target element.
The searchRange function combines the results of findFirst and findLast functions into a vector and returns it.
I hope this helps! Let me know if you have any further questions.