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

题目描述

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

思路分析

1. 题目已知数组升序,要查找目标值，因此可以使用二分查找法，时间复杂度为最低
2. 使用二分查找找到目标值，如果没有找到目标值，说明数组中没有目标值，则直接返回[-1 , -1]
3. 若找到目标值，然后考虑如何判断该元素是不是数组中第一次出现或者最后一次出现
4. 可以使用循环比较的方法，每次索引 -1 ，如果相同，则记录并执行相同的操作，否则结束循环
5. 具体如下

源码及分析

public int[] searchRange(int[] nums, int target) {
        //定义数组保存返回的索引
        int[] res = new int[]{-1, -1};
        int len = nums.length;
        //数据校验
        if (nums == null || len == 0) {
            return res;
        }
        //因为数组是升序的，因此可以使用二分查找法查找目标值
        int left = 0, right = len - 1, index = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                index = mid;
                break;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        //如果没找到目标值，直接返回[-1,-1]
        if (index == -1) {
            return res;
        }
        //如果找到目标值，记录当前目标值索引
        int temp = index;
        //先给返回值赋值
        res[0] = index;
        res[1] = index;
        //然后判断当前索引是不是数组中第一次出现的位置，若不是，修改索引
        while (index > 0 && nums[index] == nums[index - 1]) {
            index--;
            res[0] = index;
        }
        index = temp;
        //判断当前索引是不是最后一次出现的元素，如果不是，修改索引
        while (index < len - 1 && nums[index] == nums[index + 1]) {
            index++;
            res[1] = index;
        }
        return res;
    }