“This is the 20th time I have participated in the November Gwen Challenge. See details: 2021 Last Gwen Challenge”
Topic describes
Given an array of integers in ascending order, nums, and a target value, target. Find the starting and ending positions of the given target value in the array.
If no target value exists in the array, return [-1, -1].
- Example 1:
Enter nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]
- Example 2:
Enter nums = [5,7,7,8,8,10], target = 6
Output: [1, 1]
- Example 3
Enter: nums = [], target = 0
Output: [1, 1]
- The advanced
- You can design and implement a time complexity of zero
O(log n)Does the algorithm solve this problem?
- Tip:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- Nums is a non-decrement array
- -109 <= target <= 109
Subject analysis
Nums [start] = target; nums[end] = target; nums[start] = target
If nums[mid] = target (idx, idX, idX, idX, idX, idX, idX); Otherwise, start = mid + 1, that is, continue to search for larger indices that may exist.
class Solution {
public int[] searchRange(int[] nums, int target) {
int start_idx = binarySearch(nums, 0, nums.length - 1, target, true);
if(start_idx == -1){
return new int[]{-1, -1};
}
int upper_idx = binarySearch(nums, 0, nums.length - 1, target, false);
return new int[]{start_idx, upper_idx};
}
public int binarySearch(int[] nums, int start, int end, int target, boolean isLower){
int idx = -1;
while(start <= end){
if(nums[start] == target && isLower){
return start;
}
if(nums[end] == target && !isLower){
return end;
}
int mid = (start + end) / 2;
if(nums[mid] < target){
start = mid + 1;
}else if(nums[mid] > target){
end = mid - 1;
}else{
idx = mid;
if(isLower){
end = mid - 1;
}else{
start = mid + 1;
}
}
}
return idx;
}
}
Copy the code