Problem:?34. 在排序數組中查找元素的第一個和最后一個位置

1. 題目描述
2. 思路
3. 解題方法
4. 復雜度
5. Code

題目描述

34. 在排序數組中查找元素的第一個和最后一個位置

力扣鏈接

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
如果數組中不存在目標值 target，返回 [-1, -1]。
進階：你可以設計并實現時間復雜度為?O(log?n)O(\log n)O(logn)?的算法解決此問題嗎？

示例 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]

思路

二分查找

解題方法

1.二分查找找到定位
2.向左找左邊界，向右找右邊界

復雜度

時間復雜度:

O(log n)

空間復雜度:

O(1)

Code

Java

class Solution {public int[] searchRange(int[] nums, int target) {int loc = searchLocation(nums, target);if(loc == -1){return new int[]{-1,-1};}int leftLoc = loc, rightLoc = loc;// 找左邊界while(leftLoc - 1 >= 0 && nums[leftLoc-1] == target) {leftLoc--;}// 找右邊界while(rightLoc + 1 < nums.length && nums[rightLoc+1] == target){rightLoc++;}return new int[]{leftLoc, rightLoc};}public int searchLocation(int[] nums, int target){int len = nums.length;int left = 0, right = len-1;while (left <= right){int mid = left + (right-left)/2;if(nums[mid] > target) {right = mid -1;} else if (nums[mid] < target){left = mid + 1;} else {return mid;}}return -1;}
}