Leetcode t34: find the first and last positions of elements in a sorted array

Title Description

Give you an array of integers in non decreasing order nums, And a target value target. Please find out the start position and end position of the given target value in the array .

If the target value does not exist in the array target, return [-1, -1].

You must design and implement a time complexity of O(log n) The algorithm to solve this problem .

Example 1：

Input ：nums = [5,7,7,8,8,10], target = 8
Output ：[3,4]

Example 2：

Input ：nums = [5,7,7,8,8,10], target = 6
Output ：[-1,-1]

Example 3：

Input ：nums = [], target = 0
Output ：[-1,-1]

Ideas

To meet the $O(\log n)$ Complexity , To use binary search .

Can find (target-0.5) The location of , representative target The beginning of ;
By finding (target+0.5) The location of , find target At the end of .

however , Pay attention to the boundary situation . for example ：
nums = [5,7,7,8,8,10], target = 8
If you want to find 7.5 The subscript $in{d}_l$, Then get the subscript 3; If you want to find 8.5 The subscript $in{d}_r$, Then get the subscript 5, So we need to add some operations ：
If $nums[in{d}_l]<target$, that $in{d}_l++$
If $nums[in{d}_l]>target$, that $in{d}_l--$

Code

	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;
    }