LeetCode.034.Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置
题目描述
34 Find First and Last Position of Element in Sorted Array https://leetcode-cn.com/problems/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]
解题过程
二分搜索,mid匹配指定元素后,向前后扩展找到左右边界,最坏情况下时间复杂度为 O(n)
,比如数组元素全是target元素时
题解中多数都是2次二分搜索,一次找左边界,一次找右边界,时间复杂度为 O(logn)
private static class SolutionV2020 {
public int[] searchRange(int[] nums, int target) {
int left = -1, right = -1;
if (null == nums || 0 == nums.length) {
return new int[]{left, right};
}
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
left = mid;
while (left-1 >=0 && nums[left-1] == target) {
left--;
}
right = mid;
while (right+1 < nums.length && nums[right+1] == target) {
right++;
}
break;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return new int[] {left, right};
}
}
GitHub代码
algorithms/leetcode/leetcode/_034_FindFirstAndLastPositionOfElementInSortedArray.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_034_FindFirstAndLastPositionOfElementInSortedArray.java