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

题目描述:

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

示例 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
2
3
4
5
6
7
8
9
10
11
12
13
思路：

利用二分思想先找其左边界，再找其右边界即可，注意找左边界的时候，由右侧逼近；找右边界的时候，由左侧逼近，即可。

1、首先，在 nums 数组中二分查找得到第一个大于等于 target的下标leftBorder；
2、在 nums 数组中二分查找得到第一个大于等于 target+1的下标， 减1则得到rightBorder；
3、如果开始位置在数组的右边或者不存在target，则返回[-1, -1] 。否则返回[leftBorder, rightBorder]

class Solution {

public int[] searchRange(int[] nums, int target) {

    // 判空
    if (null == nums) {
        return new int[]{-1, -1};
    }
    if (nums.length == 0) {
        return new int[]{-1, -1};
    }

    // 获取数组长度
    int len = nums.length;

    // 存储结果
    int[] res = new int[]{-1, -1};

    // 头指针和尾指针
    int left = 0, right = len - 1;

    // 二分法遍历
    while (left <= right) {
        // 获取中间索引
        int mid = (left + right) / 2;

        // 判断中间值与目标值
        if (target < nums[mid]) {
            // 中间值更大，往前面找
            right = mid - 1;
            continue;
        }
        if (target > nums[mid]) {
            // 中间值更小，往后面找
            left = mid + 1;
            continue;
        }
        if (target == nums[mid]) {
            // 中间值等于目标值，则往前和往后依次找到目标值的开始索引和结束索引
            int i = mid - 1;
            // 找开始位置
            while (i >= left) {
                if (nums[i] != target) {
                    res[0] = i + 1;
                    // 找到直接结束循环
                    break;
                }
                i--;
            }
            // 判断是否找到最后
            if (i == left - 1) {
                // 说明最左边就是开始位置
                res[0] = left;
            }

            // 找结束位置
            i = mid + 1;
            while (i <= right) {
                if (nums[i] != target) {
                    res[1] = i - 1;
                    // 找到直接结束循环
                    break;
                }
                i++;
            }
            // 判断是否找到最后
            if (i == right + 1) {
                // 说明最右边就是结束位置
                res[1] = right;
            }

            // 两个都找到之后，直接结束循环即可
            break;
        }
    }

    // 返回结果
    return res;
}

}