题目详情
给你一个依照非递加顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始地位和完结地位。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现工夫复杂度为 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] <= 109nums是一个非递加数组-109 <= target <= 109
解题思路
办法1 线性查找
首先，咱们从右边对nums进行线性扫描，当咱们找到一个指标实例时就会中断。如果咱们从不中断，那么指标就不存在，所以咱们能够提前返回“-1，-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; }}办法二 二分查找
除了用于查找左右索引自身的子例程之外，整体算法与线性扫描办法的工作形式十分类似。,在这里，咱们应用批改后的二分查找来搜寻已排序的数组，并进行一些小的调整。,首先，因为咱们正在定位蕴含指标的最右边（或最左边）索引（而不是在咱们找到指标时返回true），所以算法一找到匹配就不会终止。,相同，咱们持续搜寻直到lo == hi并且它们蕴含能够找到指标的索引。
,另一个变动是引入了左参数，这是一个布尔值，示意在target == nums [mid]的事件中要做什么;,如果右边是真的，那么咱们在关系上的左子数组上“递归”,否则，咱们在右子数组上递归。要理解为什么这是正确的，请思考咱们在索引i处找到指标的状况。,最右边的指标不能呈现在大于i的任何索引处，因而咱们永远不须要思考正确的子阵列。,雷同的参数实用于最左边的索引。
class Solution { // returns leftmost (or rightmost) index at which `target` should be // inserted in sorted array `nums` via binary search. private int extremeInsertionIndex(int[] nums, int target, boolean left) { int lo = 0; int hi = nums.length; while (lo < hi) { int mid = (lo + hi) / 2; if (nums[mid] > target || (left && target == nums[mid])) { hi = mid; } else { lo = mid+1; } } return lo; } public int[] searchRange(int[] nums, int target) { int[] targetRange = {-1, -1}; int leftIdx = extremeInsertionIndex(nums, target, true); // assert that `leftIdx` is within the array bounds and that `target` // is actually in `nums`. if (leftIdx == nums.length || nums[leftIdx] != target) { return targetRange; } targetRange[0] = leftIdx; targetRange[1] = extremeInsertionIndex(nums, target, false)-1; return targetRange; }}社区最佳答案
编程语言：java
运行工夫：4ms
战败比例：beat 100%
class Solution { public int[] searchRange(int[] nums, int target) { int start = 0, end = nums.length - 1; int[] res = new int[2]; Arrays.fill(res, -1); while (start <= end) { int mid = start + (end - start) / 2; if (nums[mid] < target) { start = mid + 1; } else if (nums[mid] > target) { end = mid - 1; }// if (nums[start] == target && res[0] == -1) {// res[0] = start;// while (mid <= end) {//// }// } if (nums[mid] == target) { res[0] = findFirst(nums, start, mid, target); res[1] = findEnd(nums, mid, end, target); return res;// int temp = mid;// while (start <= mid) {// temp = start + (temp - start) / 2;// if (nums[temp] < target) {// start = temp + 1;// }//// if (start == mid// || (nums[start] == target && (start - 1 < 0 || nums[start - 1] < target))) {// res[0] = start;// break;// } else if (start == temp) {// start++;// }// }//// temp = mid;// while (mid <= end) {// temp = temp + (end - temp) / 2;// if (nums[temp] > target) {// end = temp - 1;// }//// if (temp == mid// || nums[temp] == target && (temp + 1 >= nums.length || nums[temp + 1] > target)) {// res[1] = temp;// break;// } else if (temp == end) {// end--;// }// }//// return res; } } return res; } private int findFirst(int[] nums, int start, int end, int target) { while (start < end) { int temp = start + (end - start) / 2; if (nums[temp] < target) { start = temp + 1; } else if (nums[temp] == target) { end = temp; } } return start; } private int findEnd(int[] nums, int start, int end, int target) { while (start < end) { int temp = start + (end - start + 1) / 2; if (nums[temp] > target) { end = temp - 1; } else if (nums[temp] == target) { start = temp; } } return start; }}编程语言：javascript
运行工夫：52ms
战败比例：beat 100%
/** * @param {number[]} nums * @param {number} target * @return {number[]} */let searchRange = function(nums, target) { let sl = 0; let sm = 0; let sr = nums.length - 1; let el = 0; let em = 0; let er = nums.length - 1; while (sl < sr || el < er) { if (sl < sr) { sm = Math.floor((sl + sr) / 2); if (nums[sm] < target) { sl = sm + 1; } else { sr = sm; } } if (el < er) { em = Math.ceil((el + er) / 2); if (nums[em] > target) { er = em - 1; } else { el = em; } } } return nums[sl] === target ? [sl, er] : [-1, -1];};编程语言：python
运行工夫：24ms
战败比例：beat 100%
class Solution(object): def searchRange(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ if not nums: return [-1, -1] left = 0 right = len(nums) - 1 while left <= right: mid = (left + right) / 2 if nums[mid] == target: left = mid right = mid while left >= 0 and nums[left] == target: left -= 1 while right <= len(nums) - 1 and nums[right] == target: right += 1 return [left + 1, right - 1] elif nums[mid] > target: right = mid - 1 else: left = mid + 1 return [-1,-1] 编程语言：python3
运行工夫：40ms
战败比例：beat 100%
class Solution: def searchRange(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ def binary_find(nums,left,right,k): res = [-1,-1] if not nums:return res while left<right and nums[left]!=nums[right]: mid = (left+right)//2 if nums[mid]==k: if nums[left]<k: left += 1 if nums[right]>k: right -=1 elif nums[mid]<k: left = mid+1 else: right = mid-1 if nums[left]==k and nums[right]==k: return [left,right] else:return [-1,-1] return binary_find(nums,0,len(nums)-1,target) 编程语言：cpp
运行工夫：4ms
战败比例：beat 100%
static const auto _____ = []() { ios::sync_with_stdio(false); cin.tie(nullptr); return nullptr;}();class Solution {public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> resultVec(2, -1); int indexPre; if ((resultVec[0] = Findpre(nums, target)) != -1) { resultVec[1] = FindLast(nums, target); } return resultVec; } int Findpre(vector<int>&nums, int target) { int low = 0; int high = nums.size() - 1; while (low <= high) { int middle = (low + high) / 2; if (nums[middle]<target) low = middle + 1; if (nums[middle]>target) high = middle - 1; if (nums[middle] == target) { if (middle - 1 == -1 || nums[middle - 1]<target) return middle; else { high = middle - 1; } } } return -1; } int FindLast(vector<int>&nums, int target) { int low = 0; int high = nums.size() - 1; while (low <= high) { int middle = (low + high) / 2; if (nums[middle]<target) low = middle + 1; if (nums[middle]>target) high = middle - 1; if (nums[middle] == target) { if (middle + 1 == nums.size() || nums[middle + 1]>target) return middle; else { low = middle + 1; } } } return -1; }};编程语言：c
运行工夫：4ms
战败比例：beat 100%
/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */int* searchRange(int* nums, int numsSize, int target, int* returnSize) { int *res; *returnSize = 2; res = (int*)malloc(sizeof(int) * 2); res[0] = -1; res[1] = -1; int i; int flag = 0; //开始标记 for (i = 0; i < numsSize; i++) { if (nums[i] == target && !flag) { res[0] = i; flag = 1; } if (nums[i] == target && flag &&( i==numsSize-1 || i<numsSize-1 && nums[i+1]>target)) { *(res + 1) = i; break; } } return res;}编程语言：swift
运行工夫：16ms
战败比例：beat 100%
class Solution { func searchRange(_ nums: [Int], _ target: Int) -> [Int] { var left = 0 var right = nums.count - 1 var mid = 0 var first = -1 // 寻找第一个呈现target的地位 while left <= right { mid = left + (right - left)/2 if nums[mid] >= target { right = mid - 1 } else { left = mid + 1 } if nums[mid] == target { first = mid } } // 如果找不到第一个间接返回 if first == -1 { return [first ,first] } // 寻找最初一个呈现target的地位 var last = -1 left = first right = nums.count - 1 while left <= right { mid = left + (right - left)/2 if nums[mid] > target { right = mid - 1 } else { left = mid + 1 } if nums[mid] == target { last = mid } } return [first,last] }}参考资料
文内各种编程语言的最佳答案参考自 “算法面试宝典” 小程序，小程序内每个题目都有具体的解题报告，还有大厂面试真题，值得一用。wx扫码可关上。