leetcode 34.在排序数组中查找元素的第一个和最后一个位置（Java 二分查找 medium 重要）...

墨蓝 2023-08-17 17:01 123阅读 0赞

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

二分查找详解：

[https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/][https_leetcode-cn.com_problems_find-first-and-last-position-of-element-in-sorted-array_solution_er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula]

class Solution {
        public int[] searchRange(int[] nums, int target) {
            int left=left_bound(nums,target);
            int right=right_bound(nums,target);
            return new int[]{left,right};
        }
        int left_bound(int[] nums, int target) {
            int l=0,h=nums.length;
            while(l<h){
                int mid=l+(h-l)/2;
                if(nums[mid]==target){
                    h=mid;
                }
                else if(nums[mid]>target){
                    h=mid;
                }
                else if(nums[mid]<target){
                    l=mid+1;
                }
            }
            if(l==nums.length) return -1;
            return nums[l]==target ? l : -1;
        }
        
        int right_bound(int[] nums, int target) {
            int l=0,h=nums.length;
            while(l<h){
                int mid=l+(h-l)/2;
                if(nums[mid]==target){
                    l=mid+1;
                }else if(nums[mid]<target){
                    l=mid+1;
                }
                else{
                    h=mid;
                }
            }
            if(l==0) return -1;
            return nums[l-1]==target ? l-1 :-1;
        }
    }

转载于:https://www.cnblogs.com/y1040511302/p/11601878.html

[https_leetcode-cn.com_problems_find-first-and-last-position-of-element-in-sorted-array]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[https_leetcode-cn.com_problems_find-first-and-last-position-of-element-in-sorted-array_solution_er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/