Heading

34.在排序数组中查找元素的第一个和最后一个位置 (opens new window)

Tags: algorithms linkedin array binary-search

Langs: c cpp csharp dart elixir erlang golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (43.13%)
• Likes: 2644
• Dislikes: -
• Total Accepted: 945.4K
• Total Submissions: 2.2M
• Testcase Example: '[5,7,7,8,8,10]\n8'

给你一个按照非递减顺序排列的整数数组 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] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

/*
 * @lc app=leetcode.cn id=34 lang=javascript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  const binarySearch = (left, right) => {
    if (right < left) {
      return [-1, -1]
    }
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] === target) {
      let min = mid
      while (min > 0 && nums[min - 1] === target) {
        min--
      }
      let max = mid
      while (max < nums.length - 1 && nums[max + 1] === target) {
        max++
      }
      return [min, max]
    } else if (nums[mid] > target) {
      return binarySearch(left, mid - 1)
    } else {
      return binarySearch(mid + 1, right)
    }
  }
  return binarySearch(0, nums.length - 1)
}
// @lc code=end