2021-02-16 34. 在排序数组中查找元素的第一个和最后

题目地址

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目描述

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

进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 
示例 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]
 
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

思路

有序的序列中查找，典型的二分查找案例。
我们可以找到第一次出现的位置，往后看后面有没有，
也可以直接查找元素出现的位置，往前找第一次出现的位置，往后找第最后一次出现的位置。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/16 12:32 下午
 */
public class SearchRange {
    public static void main(String[] args) {
        int[] arr = {5,7,7,8,8,10};
        int k = 8;
        int[] result = searchRange(arr, k);
        System.out.println(result[0] + " " + result[1]);

        result = searchRangeV2(arr, k);
        System.out.println(result[0] + " " + result[1]);
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.7 MB, 在所有 Java 提交中击败了44.10%用户
     */
    private static int[] searchRangeV2(int[] arr, int target) {
        int[] result = {-1,-1};
        if (arr.length < 1) {
            return result;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        if (arr[left] != target) {
            return result;
        }
        result[0] = left;
        result[1] = getEndPos(arr, left, target);
        return result;
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.6 MB, 在所有 Java 提交中击败了59.39%用户
     */
    public static int[] searchRange(int[] arr, int target) {
        int[] result = {-1,-1};
        if (arr.length < 1) {
            return result;
        }
        int pos = splitSearch(arr, 0, arr.length - 1, target);
        if (pos != -1) {
            result[0] = getStartPos(arr, pos, target);
            result[1] = getEndPos(arr, pos, target);
        }
        return result;
    }

    private static int getEndPos(int[] arr, int right, int target) {
        int r = right+1;
        while (r < arr.length) {
            if (arr[r] != target) {
                break;
            }
            r++;
        }
        return r - 1;
    }

    private static int getStartPos(int[] arr, int left, int target) {
        int l = left-1;
        while (l >= 0) {
            if (arr[l] != target) {
                break;
            }
            l--;
        }
        return l + 1;
    }

    private static int splitSearch(int[] arr, int left, int right, int target) {
        if (left >= right) {
            return arr[left] == target ? left : -1;
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            return splitSearch(arr, left, mid, target);
        } else {
            return splitSearch(arr, mid + 1, right, target);
        }
    }
}