Find First and Last Position of Element in Sorted Array (M)

题目

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given targetvalue.

Your algorithm‘s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

题意

在给定的递增数组中找到目标值出现的第一个位置和最后一个位置，未找到目标值则返回[-1, -1]。

思路

查找第一个位置时，通过二分法找到目标值后，先向左递归看左侧是否仍存在目标值，存在则返回递归值，不存在则返回当前值；同理可查找最后一个位置。

代码实现

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 当不存在目标值时，必然有 first = last = -1
        int first = binarySearch(nums, 0, nums.length - 1, target, true);
        int last = first == -1 ? -1 : binarySearch(nums, 0, nums.length - 1, target, false);
        return new int[]{first, last};
    }

    private int binarySearch(int[] nums, int left, int right, int target, boolean findLeft) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                int value;
                // 每次先判断在左/右侧是否仍存在目标值
                if (findLeft) {
                    value = binarySearch(nums, left, mid - 1, target, true);
                } else {
                    value = binarySearch(nums, mid + 1, right, target, false);
                }
                return value == -1 ? mid : value;
            }
        }
        return -1;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  let left = 0, right = nums.length - 1
  let res = []
  // 找出现的第一个位置
  while (left < right) {
    let mid = Math.trunc((right - left) / 2) + left
    if (nums[mid] === target) {
      right = mid
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  if (nums[left] !== target) {
    return [-1, -1]
  }
  res.push(left)
  // 找出现的最后一个位置
  left = 0, right = nums.length
  while (left < right) {
    let mid = Math.trunc((right - left) / 2) + left
    if (nums[mid] > target) {
      right = mid
    } else {
      left = mid + 1
    }
  }
  res.push(left - 1)
  return res
}

0034. Find First and Last Position of Element in Sorted Array (M)

原文：https://www.cnblogs.com/mapoos/p/13193678.html