給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums菱父，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置季春。
如果數(shù)組中不存在目標(biāo)值 target馒胆，返回 [-1, -1]。
進(jìn)階：
你可以設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(log n) 的算法解決此問題嗎讯沈？
示例 1：
輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]
示例 2：
輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]
示例 3：
輸入：nums = [], target = 0
輸出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一個(gè)非遞減數(shù)組
-109 <= target <= 109
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有郁岩。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處缺狠。
解題思路及方法
O(n)很簡單问慎，一次遍歷即可，直接看進(jìn)階挤茄。
類似于33. 搜索旋轉(zhuǎn)排序數(shù)組如叼，要求 O(log n)，直接二分穷劈。在找到target的時(shí)候笼恰，向左右尋找其邊界，同時(shí)注意下標(biāo)不能越界歇终。
class Solution {
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
if (n == 0) return new int[]{-1, -1};
if (n == 1) return nums[0] == target ? new int[]{0, 0} : new int[]{-1, -1};
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 找到target并尋找其左右邊界
if (nums[mid] == target) {
int l = mid, r = mid;
// 尋找左邊界
while (l - 1 >= 0 && nums[l - 1] == target) l--;
// 尋找右邊界
while (r + 1 <= n - 1 && nums[r + 1] == target) r++;
return new int[]{l, r};
}
if (nums[mid] > target) right = mid - 1;
if (nums[mid] < target) left = mid + 1;
}
return new int[]{-1, -1};
}
}
結(jié)果如下：
