LeetCode(Sorting&Searching)Search for a Range

Search for a Range

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

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]

思路：因为数组有序，所以想到了二分查找，我们可以先利用二分查找找到一个匹配target的值，然后从这个值出发左右查找，直到找到不等于target的值为止，记录最长的距离。

java代码如下：

class Solution {
   public int[] searchRange(int[] nums, int target) {
        int k=binarySearch(nums,target, 0, nums.length-1);
        if(k==-1){
            int [] arr={-1,-1};
            return arr;
        }
        int temp=k;
        while(nums[temp]==target){
            temp++;
            if(temp==nums.length){
                break;
            }
        }
        while(nums[k]==target){
            k--;
            if(k==-1){
                break;
            }
        }
        int [] res=new int [2];
        res[0]=k+1;
        res[1]=temp-1;
        return res;
    }
    
    private int binarySearch(int [] arr, int target ,int low ,int high){
        while(low<=high){
            int index=low+(high-low)/2;
            if(arr[index]<target){
                low=index+1;
            }else if(arr[index]>target){
                high=index-1;
            }else{
                return index;
            }
        }
        return -1;
    }
}