当前位置 博文首页 > StudyWinter的博客：【LeetCode刷题】704. 二分查找
给定一个?n?个元素有序的（升序）整型数组?nums 和一个目标值?target ?，写一个函数搜索?nums?中的 target，如果目标值存在返回下标，否则返回 -1。
给定一个按照升序排列的整数数组 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]
?
================================================================================================
分析：
1、首先数组是有序的，因此采用二分法就比较简单了；
2、采用二分法进行判断，难点在与找到开始位置和结束位置；
3、从找到的位置开始向左右进行遍历，当左右数值不等于查找到的第一个相等的数值时，退出即可，将左右索引下标返回。
class Solution {
public int[] searchRange(int[] nums, int target) {
int len = nums.length;
//为空判断
if(len == 0){
return new int[]{-1,-1};
}
int left = 0; //左索引
int right = len; //右索引
while(left < right){
int mid = (left+right)/2; //中间索引
if(target == nums[mid]){ //找到相等的数值
int l =mid; //向左遍历索引
int r = mid; //向右遍历索引
while(l>=0&&nums[l]==nums[mid]){ //越界判断和相等判断
l--;
}
while(r<len&& nums[r] == nums[mid]){ //越界判断和相等判断
r++;
}
//l+1是因为while判断完后，l--
//r-1是因为while判断完后，r++
return new int[]{l+1,r-1};
}else if(target>nums[mid]){ //查找区间[mid+1,right]
left = mid+1;
}else{ //查找区间[left,mid]
right = mid;
}
}
return new int[]{-1,-1}; //while循环退出之后，说明没有找到
}
}
参考：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
