【問題描述】[中等]

【解答思路】

1. 線性掃描（不符合題意）

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public int[] searchRange(int[] nums, int target) {int[] targetRange = {-1, -1};// find the index of the leftmost appearance of `target`.for (int i = 0; i < nums.length; i++) {if (nums[i] == target) {targetRange[0] = i;break;}}// if the last loop did not find any index, then there is no valid range// and we return [-1, -1].if (targetRange[0] == -1) {return targetRange;}// find the index of the rightmost appearance of `target` (by reverse// iteration). it is guaranteed to appear.for (int j = nums.length-1; j >= 0; j--) {if (nums[j] == target) {targetRange[1] = j;break;}}return targetRange;} }

2. 二分法（排除法）

如果是找第 1 次出現(xiàn)的下標(biāo)，先想到 nums[mid] < target 有一方面的原因是，找第 1 次出現(xiàn)的下標(biāo)，是找靠左的元素，所以就得按照 →→→→→→ 這個(gè)方向去逼近。

如果是找最后 1 次出現(xiàn)的下標(biāo)，是找靠右的元素，所以就得按照 ???????????? 這種方式去逼近。其實(shí)完全可以分析得再細(xì)一點(diǎn)，就看 ==、> 和 < 的情況，下一輪搜索的區(qū)間在那里，可能更具體一些。

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

public class Solution {public int[] searchRange(int[] nums, int target) {int len = nums.length;if (len == 0) {return new int[]{-1, -1};}int firstPosition = findFirstPosition(nums, target);if (firstPosition == -1) {return new int[]{-1, -1};}int lastPosition = findLastPosition(nums, target);return new int[]{firstPosition, lastPosition};}private int findFirstPosition(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = (left + right) >>> 1;// 小于一定不是解if (nums[mid] < target) {// 下一輪搜索區(qū)間是 [mid + 1, right]left = mid + 1;} else {right = mid;}}if (nums[left] == target) {return left;}return -1;}private int findLastPosition(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = (left + right + 1) >>> 1;// 大于一定不是解if (nums[mid] > target) {// 下一輪搜索區(qū)間是 [left, mid - 1]right = mid - 1;} else {left = mid;}}return left;} }

【總結(jié)】

1.[算法][二分查找][排除法]總結(jié)

2. 搜索區(qū)間問題

• 如果是找第 1 次出現(xiàn)的下標(biāo)，先想到 nums[mid] < target 有一方面的原因是，找第 1 次出現(xiàn)的下標(biāo)，是找靠左的元素，所以就得按照 →→→→→→ 這個(gè)方向去逼近。
• 如果是找最后 1 次出現(xiàn)的下標(biāo)，是找靠右的元素，所以就得按照 ???????????? 這種方式去逼近。其實(shí)完全可以分析得再細(xì)一點(diǎn)，就看 ==、> 和 < 的情況，下一輪搜索的區(qū)間在那里，可能更具體一些。

3. 出現(xiàn) left = mid 記得取中間值要 mid = (left + right + 1) >>> 1，避免死循環(huán)

參考鏈接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/si-lu-hen-jian-dan-xi-jie-fei-mo-gui-de-er-fen-cha/

參考鏈接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-/

總結(jié)

以上是生活随笔為你收集整理的[Letcode]第[34]题[JAVA][在排序数组中查找元素的第一个和最后一个位置][暴力][二分]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。