34.在排序數(shù)組中查找元素的第一個和最后一個位置
給你一個按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個目標值 target。請你找出給定目標值在數(shù)組中的開始位置和結(jié)束位置。
如果數(shù)組中不存在目標值 target，返回 [-1, -1]。
你必須設(shè)計并實現(xiàn)時間復(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]
提示：文章來源：http://www.zghlxwxcb.cn/news/detail-793521.html
0 <= nums.length <= 105-109 <= nums[i] <= 109-
nums是一個非遞減數(shù)組 -109 <= target <= 109
該題考察的是二分法，二分法求左右邊界問題文章來源地址http://www.zghlxwxcb.cn/news/detail-793521.html
//荷蘭國旗問題，兩次二分
public class Problem_0034_FindFirstAndLastPositionOfElementInSortedArray {
public static int[] searchRange(int[] nums, int target) {
int[] ans = { -1, -1 };
if (nums == null || nums.length == 0) {
return ans;
}
ans[0] = findFirst(nums, target);
ans[1] = findLast(nums, target);
return ans;
}
public static int findFirst(int[] arr, int num) {
int L = 0;
int R = arr.length - 1;
int ans = -1;
int mid = 0;
while (L <= R) {
mid = L + ((R - L) >> 1);
if (arr[mid] < num) {
L = mid + 1;
} else if (arr[mid] > num) {
R = mid - 1;
} else {
ans = mid;
// 此處因為要找的target最左邊界，所有移動R為mid - 1，再看左邊還有沒有target值
R = mid - 1;
}
}
return ans;
}
public static int findLast(int[] arr, int num) {
int L = 0;
int R = arr.length - 1;
int ans = -1;
int mid = 0;
while (L <= R) {
mid = L + ((R - L) >> 1);
if (arr[mid] < num) {
L = mid + 1;
} else if (arr[mid] > num) {
R = mid - 1;
} else {
ans = mid;
// 此處因為要找的target最右邊界，所有移動L為mid + 1，再看右邊還有沒有target值
L = mid + 1;
}
}
return ans;
}
}
到了這里，關(guān)于34.在排序數(shù)組中查找元素的第一個和最后一個位置的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
