LeetCode|【刷题1】LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 java题解 leetcode|java|二分查找|数组|算法

【LeetCode|【刷题1】LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 java题解】2021.08.08更新：
据评论指出，原先的代码在用例为[2,2],1时不能通过。
原因是找不到时，数组下标越界。
目前的解决方法是在循环判断条件那里限制了左右边界的合法范围。
代码已修改。
1.题目 https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

文章图片

2.分析两次二分查找过程，分别找最小下标和最大下标。
3.代码

class Solution { public static void main(String[] args) { int[] nums={2,2}; Solution s=new Solution(); int[] res=s.searchRange(nums,1); System.out.println(res[0]); System.out.println(res[1]); } public int[] searchRange(int[] nums, int target) { int[] res=new int[]{-1,-1}; if(nums==null||nums.length==0) return res; if(nums.length==1&&nums[0]!=target) return res; int left=0; int right=nums.length-1; while(left<=right&&left>=0&&left=0&&right=left&&nums[mid-1]==nums[mid]){ right=mid-1; } //左边无相同值，说明这就是第一个位置，找到了，退出循环 else{ res[0]=mid; break; } } else if(nums[mid]>target){ right=mid-1; } else{ left=mid+1; } }left=res[0]; //把左边界的值设为left，这样范围小点 right=nums.length-1; while(left<=right&&left>=0&&left=0&&righttarget){ right=mid-1; } else{ left=mid+1; } } return res; } }

4.复杂度时间复杂度：O(logn)。由于二分查找每次将搜索区间大约划分为两等分，所以至多有ceil?log 2n? 次迭代。二分查找的过程被调用了两次，所以总的时间复杂度是对数级别的。
空间复杂度：O(1)。所有工作都是原地进行的，所以总的内存空间是常数级别的。
5.结果