LeetCode.034.Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置

题目描述

34 Find First and Last Position of Element in Sorted Array
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

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

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]

---

解题过程

二分搜索，mid匹配指定元素后，向前后扩展找到左右边界，最坏情况下时间复杂度为 O(n)，比如数组元素全是target元素时
题解中多数都是2次二分搜索，一次找左边界，一次找右边界，时间复杂度为 O(logn)

private static class SolutionV2020 {
    public int[] searchRange(int[] nums, int target) {
        int left = -1, right = -1;
        if (null == nums || 0 == nums.length) {
            return new int[]{left, right};
        }
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                left = mid;
                while (left-1 >=0 && nums[left-1] == target) {
                    left--;
                }
                right = mid;
                while (right+1 < nums.length && nums[right+1] == target) {
                    right++;
                }
                break;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return new int[] {left, right};
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_034_FindFirstAndLastPositionOfElementInSortedArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_034_FindFirstAndLastPositionOfElementInSortedArray.java

---