JAVA练习338- 在排序数组中查找元素的第一个和最后一个位置

题目概览给你一个按照非递减顺序排列的整数数组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 10^5-10^9 nums[i] 10^9nums是一个非递减数组-10^9 target 10^9来源34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode解题分析方法二分查找因为数组是非递减的因此可以用二分法来实现。此题要求我们找到 target 的最左边索引和最右边索引令中间索引为 mid实际就是看对 nums[ mid ] target 时的处理当 nums[ mid ] target 时最左边索引不是 mid 就是在 mid 左边因此记录 mid然后收缩左边界 即 j mid - 1当 nums[ mid ] target 时最右边索引不是 mid 就是在 mid 右边因此记录 mid然后收缩右边界 即 i mid 1因此可以用一个 flag 标识是求左边索引还是右边索引调用两次方法返回结果即可。时间复杂度O(logn)空间复杂度O(1)class Solution { public int[] searchRange(int[] nums, int target) { int left searchRange(nums, target, true); int right searchRange(nums, target, false); if (left right left 0 right nums.length) { return new int[]{left, right}; } return new int[]{-1,-1}; } public int searchRange(int[] nums, int target, boolean isLeft) { int n nums.length; int i 0, j n - 1, ans -1; while(i j) { int mid (i j) / 2; if (nums[mid] target) { ans mid; if (isLeft) { j mid - 1; } else { i mid 1; } } else if (nums[mid] target) { j mid - 1; } else { i mid 1; } } return ans; } }