34. Find First and Last Position of Element in Sorted Array
Description
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Follow up: Could you write an algorithm with O(log n) runtime complexity?
Constraints
0 <= nums.length <= 105-109 <= nums[i] <= 109numsis a non-decreasing array.-109 <= target <= 109
Approach
Links
GeeksforGeeks
YouTube
Examples
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]
Input: nums = [], target = 0
Output: [-1, -1]
Solutions
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[]{-1, -1};
if(nums == null || nums.length == 0) return result;
int index = binarySearch(nums, target, 0, nums.length-1);
if(index == -1) return result;
result[0] = index;
result[1] = index;
int i = index;
while(i > 0 && nums[i-1] == target) {
i = binarySearch(nums, target, 0, i-1);
if(result[0] == i) break;
if(i != -1) result[0] = i;
}
i = index;
while(i < nums.length-1 && nums[i+1] == target) {
i = binarySearch(nums, target, i+1, nums.length);
if(result[1] == i) break;
if(i != -1) result[1] = i;
}
return result;
}
private int binarySearch(int[] nums, int target, int low, int high) {
while(low <= high) {
int mid = (low+high)/2;
if(nums[mid] == target) {
return mid;
}
if(nums[mid] < target) {
low = mid+1;
} else {
high = mid-1;
}
}
return -1;
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
if(nums == null || nums.length == 0) {
return result;
}
int n = nums.length;
int index = binarySearch(nums, target, 0, n-1);
if(index >= 0) {
int lower = index;
while(lower > 0 && nums[lower-1] == target) {
int tmpIdx = binarySearch(nums, target, 0, lower-1);
if(tmpIdx >= 0) {
lower = tmpIdx;
} else {
break;
}
}
result[0] = lower;
int higher = index;
while(higher < n-1 && nums[higher+1] == target) {
int tmpIdx = binarySearch(nums, target, higher+1, n-1);
if(tmpIdx >= 0) {
higher = tmpIdx;
} else {
break;
}
}
result[1] = higher;
}
return result;
}
private int binarySearch(int[] nums, int target, int low, int high) {
while(low <= high) {
int mid = low + (high-low)/2;
if(nums[mid] == target) {
return mid;
}
if(nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}Follow up
Last updated
Was this helpful?