文章目录

• 一、题目描述
• 二、解题步骤
• • 1.思路
  • 2.代码
  • 3.复杂度分析
• 三、总结

一、题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -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]

实例3：

输入：nums = [], target = 0
输出：[-1,-1]

二、解题步骤

1.思路

解法1：顺序搜索查找到第一个等于target的值，再顺序查找到第一个不等于target的值。所需要的时间复杂度为O(n);

解法2：要找到目标元素的区间，我们可以把问题分解成找到左边界再找到右边界。（使用左闭右闭区间）。
查找左边界的实例如图所示，最终返回right的值即为左边界。

查找右边界的实例如下图所示，最终返回left为右边界

2.代码

class Solution {    public int[] searchRange(int[] nums, int target) { int leftBorder = getLeft(nums,target); int rightBorder = getRight(nums,target); if(leftBorder==-2 || rightBorder==-2) return new int[]{-1,-1}; // 超出数组边界（在左边界左边/右边界往右） if(rightBorder-leftBorder>1) return new int[]{leftBorder+1,rightBorder-1}; return new int[]{-1,-1}; //数组中不存在target.    }    int getRight(int[] nums,int target){ int left = 0; int right = nums.length-1; int rightBorder = -2; while(left<=right){     int mid = left+(right-left)/2;     if(nums[mid]>target){  right = mid-1;     }else{  left = mid+1;  rightBorder = left;} }  return rightBorder;    }    int getLeft(int[] nums,int target){ int left = 0; int right = nums.length-1; int leftBorder = -2; while(left<=right){     int mid = left+(right-left)/2;     if(nums[mid]>=target){  right = mid-1;  leftBorder = right;     }else{  left = mid+1;     } } return leftBorder;    }}

3.复杂度分析

时间复杂度：O(logn)
空间复杂度：O(1)

三、总结

本题的关键在于找出左右边界。