LeetCode_二分搜索_中等_34.在排序数组中查找元素的第一个和最后一个位置

桃扇骨 2023-10-06 18:07 9阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

## 2.思路 ##

（1）二分搜索查找左/右侧边界 I  
在数组中分别寻找 target 的左右边界，然后返回即可。有关细节可以查看[【算法】二分搜索][Link 1]这篇文章。

（2）二分搜索查找左/右侧边界 II  
设计一个时间复杂度为 O(log n) 的算法来解决此问题，最容易想到的就是二分查找（来自[本题官方题解][Link 2]）：

*  首先，寻找在数组中寻找第一个大于等于 target 的下标 leftIdx，然后再寻找即为在数组中寻找第一个大于 target 的下标 rightIdx ，并将其下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 nums 数组中二分查找 target 的位置，如果 lower 为true，则查找第一个大于等于 target 的下标，否则查找第一个大于 target 的下标。
 *  因为 target 可能不存在数组中，因此我们需要重新校验我们得到的两个下标 leftIdx 和 rightIdx，看是否符合条件，如果符合条件就返回\[leftIdx, rightIdx\]，不符合就返回 \[-1, -1\]。

（3）二分搜索 & 递归

## 3.代码实现（Java） ##

//思路1————二分搜索查找左/右侧边界
    class Solution {
        
        public int[] searchRange(int[] nums, int target) {
        
            return new int[]{
        leftBoundSearch(nums, target), rightBoundSearch(nums, target)};
        }
        
        //查找左边界
        public int leftBoundSearch(int[] nums, int target) {
        
            int left = 0, right = nums.length - 1;
            //搜索区间为 [left, right]
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            //检查出界情况
            if (left >= nums.length || nums[left] != target)
                return -1;
            return left;
        }
        
        //查找右边界
        public int rightBoundSearch(int[] nums, int target) {
        
            int left = 0, right = nums.length - 1;
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                if (nums[mid] > target) {
        
                    right = mid - 1;
                } else {
        
                    left = mid + 1;
                }
            }
            // 最后要检查 right 越界的情况
            if (right < 0 || nums[right] != target)
                return -1;
            return right;
        }
    }

//思路2————来自LeetCode官方题解
    class Solution {
        
    	public int[] searchRange(int[] nums, int 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};
    	}	
    	//如果 lower 为 true，则查找第一个大于等于 target 的下标，否则查找第一个大于 target 的下标
    	public 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 - left) / 2;
    	        if (nums[mid] > target || (lower && nums[mid] >= target)) {
        
    	            right = mid - 1;
    	            ans = mid;
    	        } else {
        
    	            left = mid + 1;
    	        }
    	    }
    	    return ans;
    	}
    }

//思路3————二分搜索 & 递归
    class Solution {
        
        public int[] searchRange(int[] nums, int target) {
        
            int[] res = {
        -1, -1};
            if (nums.length == 0) {
        
                return res;
            }
            res[0] = binarySearch(nums, target, 0, nums.length - 1, true);
            res[1] = binarySearch(nums, target, 0, nums.length - 1, false);
            return res;
        }
    
        public int binarySearch(int[] nums, int target, int left, int right, boolean isLeft) {
        
            if (left > right) {
        
                return -1;
            }
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
        
                if (isLeft) {
        
                    if (mid == left || nums[mid - 1] != target) {
        
                        return mid;
                    } else {
        
                        return binarySearch(nums, target, left, mid - 1, isLeft);
                    }
                } else {
        
                    if (mid == right || nums[mid + 1] != target) {
        
                        return mid;
                    } else {
        
                        return binarySearch(nums, target, mid + 1, right, isLeft);
                    }
                }
            } else if (nums[mid] > target) {
        
                return binarySearch(nums, target, left, mid - 1, isLeft);
            } else {
        
                return binarySearch(nums, target, mid + 1, right, isLeft);
            }
        }
    }

[Link 1]: https://blog.csdn.net/weixin_43004044/article/details/128591151
[Link 2]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/