算法34. Find First and Last Position of Element in Sorted Array

34. 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]

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
    }
}

说，给一个正序的整形数组，找到目标值得起始和结束的下标。
要求时间复杂度为O(logn)。
没找到就返回[-1,-1]。

解：
要求时间复杂度为O(logn)，首先想到折半查找。折半呢，找一个数好找，找末尾呢，取个巧，找大于目标值+1的数的下标减一即可。以下为代码：

public int[] searchRange(int[] nums, int target) {
    int[] targetRange = { -1, -1 };

    int leftIdx = extremeInsertionIndex(nums, target);

    if (leftIdx == nums.length || nums[leftIdx] != target) {
        return targetRange;
    }

    targetRange[0] = leftIdx;
    targetRange[1] = extremeInsertionIndex(nums, target + 1) - 1;

    return targetRange;
}

private int extremeInsertionIndex(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length;

    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] >= target) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    return lo;
}

转载于:https://www.jianshu.com/p/4e04127fed59