力扣——在排序数组中查找元素的第一个和最后一个位置

小灰灰 2023-10-02 11:02 14阅读 0赞

##### [在排序数组中查找元素的第一个和最后一个位置][Link 1] #####

> 给定一个按照升序排列的整数数组 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

--------------------

解法一：暴力解法

--------------------

解法二：二分查找

package com.kk;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    //34. 在排序数组中查找元素的第一个和最后一个位置
    public class SearchRange {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int[] nums = new int[6];
            for (int i = 0; i < nums.length; i++) {
        
                nums[i]=scanner.nextInt();
            }
            int target=scanner.nextInt();
            int[] searchRange = searchRange(nums, target);
            System.out.println(Arrays.toString(searchRange));
        }
        public static int[] searchRange(int[] nums, int target) {
        
            //如果 \textit{lower}lower 为 \rm truetrue，则查找第一个大于等于 ltextit{target}target 的下标，
            // 否则查找第一个大于 ltextit{target}target 的下标。
    
            int leftIdx = binarySearch(nums, target, true);
            int rightIdx = binarySearch(nums, target, false) - 1;
            if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
        
                return new int[]{
        leftIdx, rightIdx};
            }
            return new int[]{
        -1, -1};
        }
    
        public static int binarySearch(int[] nums, int target, boolean lower) {
        
            int left = 0, right = nums.length - 1, ans = nums.length;
            while (left <= right) {
        
                int mid = (left + right) / 2; //使用二分查找
                if (nums[mid] > target || (lower && nums[mid] >= target)) {
        
                    right = mid - 1;
                    ans = mid;
                } else {
        
                    left = mid + 1;
                }
            }
            return ans;
    
        }
    
    }

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