文章目录

题目描述思路 & 代码1. 暴力法2. 二分法3. 二分法——简略版

题目描述

老套路了，有序找元素，直接冲二分思路是不难想，就是边界条件限制条件有点恶心，时不时爆个栈

思路 & 代码

1. 暴力法

一次遍历找到left，right。时间复杂度O(n）

2. 二分法

当然其实findLeft & findRight可以合并成一个函数，用flag来表示找left还是right。此处便于理解，就不合并了不断缩小范围，找到了就先存着，然后继续缩小范围找。

class Solution {public int[] searchRange(int[] nums, int target) {// 二分int[] ans = new int[]{-1,-1};if(nums == null || nums.length == 0){return ans;}// 初始化结束ans[0] = findLeft(nums,target);if(ans[0] != -1){ans[1] = findRight(nums,target);}return ans;}int findLeft(int[] nums,int target){int ans = -1;int left = 0, right = nums.length-1;while(left < right){int half = (right + left)/2;// 选左区间if(nums[half] > target){right = half - 1;}else if (nums[half] < target){left = half + 1;}else if (nums[half] == target){ans = half;right = half - 1;}}if(target == nums[left]){ans = left;}return ans;}int findRight(int[] nums,int target){int ans = -1;int left = 0, right = nums.length-1;while(left < right){int half = (right + left)/2;// 选左区间if(nums[half] > target){right = half - 1;}else if (nums[half] < target){left = half + 1;}else if (nums[half] == target){ans = half;left = half + 1;}}if(target == nums[right]){ans = right;}return ans;}}

3. 二分法——简略版

class Solution {public int[] searchRange(int[] nums, int target) {// 二分int[] ans = new int[]{-1,-1};if(nums == null || nums.length == 0){return ans;}// 初始化结束ans[0] = findLeftOrRight(nums, target, true);if(ans[0] != -1){ans[1] = findLeftOrRight(nums, target, false);}return ans;}int findLeftOrRight(int[] nums, int target, boolean isFindLeft){int ans = -1;int left = 0, right = nums.length-1;while(left < right){int half = (right + left) / 2;// 选左区间if(nums[half] > target){right = half - 1;}// 选右区间else if (nums[half] < target){left = half + 1;}// 根据找第一个 or 最后一个来进行赋值else if (nums[half] == target){ans = half;// 找第一个，往左区间走if(isFindLeft) {right = half - 1;}// 找最后一个，往右区间走else {left = half + 1;}}}if(target == nums[left]){ans = left;}return ans;}}

如果觉得《【LeetCode笔记】34. 在排序数组中查找元素的第一个和最后一个位置（Java 二分）》对你有帮助，请点赞、收藏，并留下你的观点哦！