LeetCode-34.在排序数组中查找元素的第一个和最后一个位置

叁歲伎倆 2022-01-28 15:47 136阅读 0赞

# 题目 #

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

**你的算法时间复杂度必须是 O(log n) 级别。**

如果数组中不存在目标值，返回 \[-1, -1\]。

###### 示例 1: ######

> 输入: nums = \[5,7,7,8,8,10\], target = 8  
> 输出: \[3,4\]

###### 示例 2: ######

> 输入: nums = \[5,7,7,8,8,10\], target = 6  
> 输出: \[-1,-1\]

解题思路—**二分思想**：题目要求搜索的**时间复杂度必须为O(log n)**，所以这题肯定采用**二分法**。下面的有两种写法：

1.  **当二分搜索中间值=target时，从中间值向两侧搜索得到边界。**
2.  **当二分搜索中间值=target时，在数组左半部分和右半部分继续二分搜索找出边界。**

## Java解题—向两侧搜索 ##

class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] res = {-1, -1};
            if(nums==null || nums.length==0)
                return res;
    
            int tar = beamSearch(nums, 0, nums.length-1, target);
            if(tar==-1)
                return res;
            int left = tar, right = tar;
            while(left-1>=0 && nums[left-1]==target)
                left--;
            while(right+1<nums.length && nums[right+1]==target)
                right++;
            res[0] = left;
            res[1] = right;
            return res;
        }
        
        public int beamSearch(int[] nums, int left, int right, int target){
            if(left>right)
                return -1;
            int mid = left + (right-left)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                return beamSearch(nums, mid+1, right, target);
            }else
                return beamSearch(nums, left, mid-1, target);
        }
    }

## Java解题—两次二分查找 ##

class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] pos = new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};
            beamSearch(nums,target,0,nums.length-1,pos);
            if(pos[0]==Integer.MAX_VALUE) 
                return new int[]{-1,-1};
            else 
                return pos;
        }
    
        public void beamSearch(int[] nums,int target,int low,int high,int[] pos){
            if(low>high) return;
            int mid=low+(high-low)/2;
            if(nums[mid]==target){
                if(mid<pos[0]) pos[0]=mid;
                if(mid>pos[1]) pos[1]=mid;
                beamSearch(nums,target,low,mid-1,pos);
                beamSearch(nums,target,mid+1,high,pos);
            }else if(nums[mid]>target)
                beamSearch(nums,target,low,mid-1,pos);
            else
                beamSearch(nums,target,mid+1,high,pos);
        }
    }