LeetCode 在排序数组中查找元素的第一个和最后一个位置【二分查找】

小灰灰 2022-09-10 12:23 183阅读 0赞

# 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

# 2 解题 #

**思路：** 剪枝 + 二分查找

public int[] searchRange(int[] nums, int target) { 
            int[] rs = new int[]{ -1, -1};
            //剪枝，长度为0，最大值小于target最小值大于target
            if (nums.length == 0 || nums[nums.length - 1] < target || nums[0] > target) { 
                return rs;
            }
            //二分查找
            int left = 0;
            int right = nums.length - 1;
    
            while (left <= right) { 
                int mid =  (left + right) / 2;
                if (nums[mid] > target) { 
                    right = mid - 1;
                } else if (nums[mid] < target) { 
                    left = mid + 1;
                } else { 
                    //mid等于target
                    for (int tempLeft = mid; tempLeft >= 0; tempLeft--) { 
                        if (tempLeft < mid && nums[tempLeft] != nums[tempLeft + 1]) { 
                            break;
                        }
                        rs[0] = tempLeft;
                    }
    
                    for (int tempRight = mid; tempRight < nums.length; tempRight++) { 
                        if (tempRight > mid && nums[tempRight] != nums[tempRight - 1]) { 
                            break;
                        }
                        rs[1] = tempRight;
                    }
                    break;
                }
            }
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/9a85db47c31044e2900cab4c86f0629e.png