来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

描述

给定一个按照升序排列的整数数组 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]

题解

  1. class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.         int firstPostion = leftBound(nums, target);
  4.         int lastPosition = rightBound(nums, target);
  6.         return new int[]{firstPostion, lastPosition};
  7.     }
  9.     private int leftBound(int[] nums, int target) {
  10.         int left = 0, right = nums.length - 1;
  11.         while (left <= right) {
  12.             int mid = left + (right - left) / 2;
  13.             if (nums[mid] == target) {
  14.                 right = mid - 1;
  15.             } else if (nums[mid] > target) {
  16.                 right = mid - 1;
  17.             } else if (nums[mid] < target) {
  18.                 left = mid + 1;
  19.             }
  20.         }
  22.         if (left >= nums.length || nums[left] != target) {
  23.             return -1;
  24.         }
  25.         return left;
  26.     }
  28.     private int rightBound(int[] nums, int target) {
  29.         int left = 0, right = nums.length - 1;
  30.         while (left <= right) {
  31.             int mid = left + (right - left) / 2;
  32.             if (nums[mid] == target) {
  33.                 left = mid + 1;
  34.             } else if (nums[mid] > target) {
  35.                 right = mid - 1;
  36.             } else if (nums[mid] < target) {
  37.                 left = mid + 1;
  38.             }
  39.         }
  41.         if (right < 0 || nums[right] != target) {
  42.             return -1;
  43.         }
  44.         return right;
  45.     }
  46. }

参考