Leetcode T34: 在排序数组中查找元素的第一个和最后一个位置

题目描述

给你一个按照非递减顺序排列的整数数组 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]

思路

要满足 $O(\log n)$ 的复杂度，要使用二分查找。

可以找到(target-0.5)的位置，代表target的开始位置；
通过找到(target+0.5)的位置，找到target的结束位置。

但是，要注意边界情况。例如：
nums = [5,7,7,8,8,10], target = 8
如果要找到7.5的下标$in{d}_l$，那么得到下标3；如果要找到8.5的下标$in{d}_r$，那么得到下标5，所以要加上一下操作：
如果$nums[in{d}_l]<target$， 那么 $in{d}_l++$
如果$nums[in{d}_l]>target$， 那么 $in{d}_l--$

代码

	int findInd(int[] nums, double target) {
    
		int l = 0, r = nums.length-1;
    	while(l < r) {
    
    		int mid = (l+r) / 2;
    		int t = nums[mid];
    		if(t == target) {
    
    			return mid;
    		} else if (t < target){
    
    			l = mid+1;
    		} else {
    
    			r = mid-1;
    		}
    	}
    	return l;
	}
	
    public int[] searchRange(int[] nums, int target) {
    
        if(nums.length == 0) {
    
            int[] t = {
    -1, -1};
            return t;
        }
    	int[] res = new int[2];
    	res[0] = findInd(nums, target-0.5);
    	res[1] = findInd(nums, target+0.5);
    	if(nums[res[0]] < target) res[0]+=1;
    	if(nums[res[1]] > target) res[1]--;
    	if(res[0] > res[1]) {
    
    		res[0] = -1;
    		res[1] = -1;
    	}
    	return res;
    }