题目:

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回  [-1, -1]。

进阶:

• 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例:

1. 示例 1:

输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

2. 示例 2:

输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

3. 示例 3:

输入：nums = [], target = 0 输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums  是一个非递减数组
• -109 <= target <= 109

抛砖引玉

思路：

一遍循环

一遍循环，记录数组中等于 target 元素的位置，如果变量到元素大于 target，则终止循环，直接返回结果

/**  * @param {number[]} nums  * @param {number} target  * @return {number[]}  */ var searchRange = function(nums, target) {
         let start = -1,         end = -1,         index = 0     while (index         if (nums[index] === target) {
                 if (start === -1) {
                     start = index                 end = index             } else {
                     end = index             }             index++         } else if (nums[index] > target) {
                 return [start, end]         } else {
                 index++         }     }     return [start, end] }

二分查找

首先二分查找出 target 所在的索引位置：

• 如果没有找到则返回[-1,-1]
• 如果找到了索引位置，则在这个索引位置的前后继续查找，找到边界索引位置

var searchRange = function(nums, target) {
         let start = -1,         end = nums.length - 1,         mid = Math.floor((start + end) / 2),         flag = false     // 找到数组中target的位置     while (start <= end) {
             mid = (start + end) / 2         if (nums[mid]             start = mid + 1         } else if (nums[mid] > target) {
                 end = mid - 1         } else {
                 flag = true             break         }     }     // 找到target边界索引位置     if (flag) {
             let left = mid,             right = mid         while (left - 1 >= 0 && nums[left - 1] == target) {
                 left--         }         while (right + 1 <= nums.length - 1 && nums[right + 1] == target) {
                 right++         }         return [left, right]     } else {
             return [-1, -1]     } }

博客: 前端小书童

每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号：前端小书童