Algorithm
Problem Name: 34. Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109numsis a non-decreasing array.-109 <= target <= 109
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int i, j, *range;
int start, end, mid;
range = malloc(2 * sizeof(int));
//assert(range);
i = j = -1;
start = 0; end = numsSize - 1;
while (start < = end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
i = j = mid;
while (i > 0 && nums[i - 1] == target) {
i --;
}
while (j < numsSize - 1 && nums[j + 1] == target) {
j ++;
}
break;
} else if (nums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
range[0] = i;
range[1] = j;
*returnSize = 2;
return range;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
if(lo > hi) return {-1,-1};
return {lo, hi};
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[]{binarySearchHelper(nums, target, -1), binarySearchHelper(nums, target, 1)};
}
private int binarySearchHelper(int[] nums, int target, int direction) {
int idx = -1;
int start = 0;
int end = nums.length - 1;
while (start < = end) {
int mid = (start + end) / 2;
if (nums[mid] == target) {
idx = idx == -1 ? mid : (direction == -1 ? Math.min(mid, idx) : Math.max(mid, idx));
if (direction == -1) {
end = mid - 1;
} else {
start = mid + 1;
}
} else if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return idx;
}
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution(object):
def searchRange(self, nums, target):
l, r = bisect.bisect_left(nums, target), bisect.bisect_right(nums, target) - 1
return [l, r] if 0 <= l <= r else [-1, -1]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _034_SearchForARange
{
public int[] SearchRange(int[] nums, int target)
{
int lo = 0, hi = nums.Length - 1, mid;
while (lo < = hi)
{
mid = lo + (hi - lo) / 2;
if (target > nums[mid])
lo = mid + 1;
else
hi = mid - 1;
}
if (lo == nums.Length || nums[lo] != target)
return new int[] { -1, -1 };
var result = new int[2];
result[0] = lo;
lo = 0; hi = nums.Length - 1;
while (lo < = hi)
{
mid = lo + (hi - lo) / 2;
if (target >= nums[mid])
lo = mid + 1;
else
hi = mid - 1;
}
result[1] = lo - 1;
return result;
}
}
}
Input
Output