34_在排序数组中查找元素的第一个和最后一个位置

类型：数组

• 34. 在排序数组中查找元素的第一个和最后一个位置 💛

  https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

  ❓ 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

  💡 二分查找

  使用二分查找：

  • 在数组中寻找第一个大于等于 target 的下标
  • 在数组中寻找第一个大于 target 的下标，然后将下标减一

  class Solution {
      public int[] searchRange(int[] nums, int target) {
          int leftIdx = binarySearch(nums, target, true);
          int rightIdx = binarySearch(nums, target, false) - 1;
          if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
              return new int[]{leftIdx, rightIdx};
          } 
          return new int[]{-1, -1};
      }
  
      public int binarySearch(int[] nums, int target, boolean lower) {
          int left = 0, right = nums.length - 1, ans = nums.length;
          while (left <= right) {
              int mid = (left + right) / 2;
              if (nums[mid] > target || (lower && nums[mid] >= target)) {
                  right = mid - 1;
                  ans = mid;
              } else {
                  left = mid + 1;
              }
          }
          return ans;
      }
  }

  时间复杂度：O(logN)，空间复杂度：O(1)