每天一题LeetCode【第25天】

T34. Search for a Range【Medium】

题目

给定以升序排序的整数数组，找到给定目标值(target)的开始和结束位置。

如果没有找到目标值，就返回[-1,-1]

注意： 算法时间复杂度必须是 O（logn）

例如，
给出数组 [5,7,7,8,8,10]
则返回 [3,4]

思路

因为是排好序的数组，所以肯定想到要用二分法。

但是这里有一个问题，如果有多个重复的目标值，怎么确定二分法找到数的恰巧是首位或者末尾的数呢，这是要说的重点。我在代码里标记了 标记1 和 标记2，问题就是在那里解决的。

找到 标记1，当 nums[mid] >= target 时，它会继续取前半段

找到 标记2，当 nums[mid] >= target 时，它会继续取后半段

这样取下去，findFirst() 方法返回的就一定是目标值得首位，而 findLast() 方法返回的就一定是目标值得末位。

当然，若找不到的话就返回 -1。

知道这个关键点其他看代码就好啦！

代码

代码取自 Top Solution，稍作注释

public class Solution {
public int[] searchRange(int[] nums, int target) {
    //初始化一个有两个元素的数组用来返回
    int[] result = new int[2];
    //找到数字的起始序号
    result[0] = findFirst(nums, target);
    //找到数字的终止序号
    result[1] = findLast(nums, target);
    return result;
}
//二分法不用多说
private int findFirst(int[] nums, int target){
    int idx = -1;
    int start = 0;
    int end = nums.length - 1;
    while(start <= end){
        int mid = (start + end) / 2;
        //标记1，在思路里说
        if(nums[mid] >= target){
            end = mid - 1;
        }else{
            start = mid + 1;
        }
        if(nums[mid] == target) idx = mid;
    }
    return idx;
}

private int findLast(int[] nums, int target){
    int idx = -1;
    int start = 0;
    int end = nums.length - 1;
    while(start <= end){
        int mid = (start + end) / 2;
        //标记2，在思路里说
        if(nums[mid] <= target){
            start = mid + 1;
        }else{
            end = mid - 1;
        }
        if(nums[mid] == target) idx = mid;
    }
    return idx;
}
}

补充

不算补充吧，算总结收获 (*•̀ㅂ•́)و。

这题让我知道了二分法还有这种细节的玩法，可以在数字重复的时候准确取得首位和末尾~