📑 题目：34. 在排序数组中查找元素的第一个和最后一个位置

🚀 本题 LeetCode 传送门

题目大意

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。

解题思路

  • 给出一个有序数组 nums 和一个数 target，要求在数组中找到第一个和这个元素相等的元素下标，最后一个和这个元素相等的元素下标。

  • 这一题是经典的二分搜索变种题。二分搜索有 4 大基础变种题：

    1. 查找第一个值等于给定值的元素
    2. 查找最后一个值等于给定值的元素
    3. 查找第一个大于等于给定值的元素
    4. 查找最后一个小于等于给定值的元素

    这一题的解题思路可以分别利用变种 1 和变种 2 的解法就可以做出此题。或者用一次变种 1 的方法，然后循环往后找到最后一个与给定值相等的元素。不过后者这种方法可能会使时间复杂度下降到 O(n)，因为有可能数组中 n 个元素都和给定元素相同。(4 大基础变种的实现见代码)

代码

  1. package leetcode
  3. func searchRange(nums []int, target int) []int {
  4.  return []int{searchFirstEqualElement(nums, target), searchLastEqualElement(nums, target)}
  6. }
  8. // 二分查找第一个与 target 相等的元素，时间复杂度 O(logn)
  9. func searchFirstEqualElement(nums []int, target int) int {
  10.  low, high := 0, len(nums)-1
  11.  for low <= high {
  12.   mid := low + ((high - low) >> 1)
  13.   if nums[mid] > target {
  14.    high = mid - 1
  15.   } else if nums[mid] < target {
  16.    low = mid + 1
  17.   } else {
  18.    if (mid == 0) || (nums[mid-1] != target) { // 找到第一个与 target 相等的元素
  19.     return mid
  20.    }
  21.    high = mid - 1
  22.   }
  23.  }
  24.  return -1
  25. }
  27. // 二分查找最后一个与 target 相等的元素，时间复杂度 O(logn)
  28. func searchLastEqualElement(nums []int, target int) int {
  29.  low, high := 0, len(nums)-1
  30.  for low <= high {
  31.   mid := low + ((high - low) >> 1)
  32.   if nums[mid] > target {
  33.    high = mid - 1
  34.   } else if nums[mid] < target {
  35.    low = mid + 1
  36.   } else {
  37.    if (mid == len(nums)-1) || (nums[mid+1] != target) { // 找到最后一个与 target 相等的元素
  38.     return mid
  39.    }
  40.    low = mid + 1
  41.   }
  42.  }
  43.  return -1
  44. }
  46. // 二分查找第一个大于等于 target 的元素，时间复杂度 O(logn)
  47. func searchFirstGreaterElement(nums []int, target int) int {
  48.  low, high := 0, len(nums)-1
  49.  for low <= high {
  50.   mid := low + ((high - low) >> 1)
  51.   if nums[mid] >= target {
  52.    if (mid == 0) || (nums[mid-1] < target) { // 找到第一个大于等于 target 的元素
  53.     return mid
  54.    }
  55.    high = mid - 1
  56.   } else {
  57.    low = mid + 1
  58.   }
  59.  }
  60.  return -1
  61. }
  63. // 二分查找最后一个小于等于 target 的元素，时间复杂度 O(logn)
  64. func searchLastLessElement(nums []int, target int) int {
  65.  low, high := 0, len(nums)-1
  66.  for low <= high {
  67.   mid := low + ((high - low) >> 1)
  68.   if nums[mid] <= target {
  69.    if (mid == len(nums)-1) || (nums[mid+1] > target) { // 找到最后一个小于等于 target 的元素
  70.     return mid
  71.    }
  72.    low = mid + 1
  73.   } else {
  74.    high = mid - 1
  75.   }
  76.  }
  77.  return -1
  78. }