Comment on page
34.Find-First-and-Last-Position-of-Element-in-Sorted-Array
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
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]
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = {-1, -1};
int leftIndex = helper(nums, target, true);
if (leftIndex == nums.length || nums[leftIndex] != target) {
return ans;
}
ans[0] = leftIndex;
ans[1] = helper(nums,target, false);
return ans;
}
private int helper(int[] nums, int target, boolean isLeft) {
int low = 0;
int high = nums.length - 1;
while (low + 1 < high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
if (isLeft) {
high = mid;
} else {
low = mid;
}
}
else if (nums[mid] > target) {
high = mid;
}
else {
low = mid;
}
}
if (isLeft) {
if (nums[low] == target) {
return low;
} else if (nums[high] == target) {
return high;
}
} else {
if (nums[high] == target) {
return high;
} else if (nums[low] == target) {
return low;
}
}
return -1;
}
}
public class Solution {
public int[] searchRange(int[] A, int target) {
if (A.length == 0) return new int[]{-1, -1};
int start, end, mid;
int[] bound = new int[2];
start = 0;
end = A.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
end = mid; // difference
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[start] == target) {
bound[0] = start;
} else if (A[end] == target) {
bound[0] = end;
} else {
bound[0] = bound[1] = -1;
return bound;
}
start = 0;
end = A.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
start = mid; // difference
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] == target) {
bound[1] = end;
} else if (A[start] == target) {
bound[1] = start;
} else {
bound[0] = bound[1] = -1;
return bound;
}
return bound;
}
}
Last modified 3yr ago