Requirements:

Given an array of integers in ascending order, nums, and a target value, target. Find the starting and ending positions of the given target value in the array.

Your algorithm must be order log n in time.

If no target value exists in the array, return [-1, -1].

Example:

Input: nums = [5,7,7,8,8,10] target = 8Copy the code
Input: nums = [5,7,7,8,8,10], target = 6Copy the code

Ideas:

Thanks labuladong for the framework.

Find the left boundary and the right boundary. Uniformly write the left and right boundaries as closed intervals. Therefore, a judgment condition should be added at the end to prevent crossing the boundary.

  • Find the left boundary:
  1. The judgment conditions in the while loop are used uniformlyleft<=right, the value of right is also the right boundary value,right=nums.length-1.
  2. nums[mid]<targetWhen,left=mid+1;
  3. nums[mid]==targetWhen,right=mid-1;
  4. nums[mid]>targetWhen,right=mid-1;
  5. And the last thing that comes back isleft.
  6. Check left if it’s out of bounds. If it’s out of bounds(left>=nums.length || nums[left] ! = target)
  • Find the right boundary:
  1. The judgment condition in the while loop also uses the interval of left-closed and right-closed, and the value is the same as above.
  2. nums[mid]<targetWhen,left=mid+1;
  3. nums[mid]==targetWhen,left=mid+1;
  4. nums[mid]>targetWhen,right=mid+1;
  5. Finally check for overstepping boundaries.

code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        int left = -1;
        int right = -1;
        left = leftBound(nums, target);
        right = leftBound(nums, target);
        res[0] = left;
        res[1] = right;
        return res;
    }
    
    public int leftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        while(left <= right) {
            mid = left + (right-left)/2;
            if(nums[mid] > target) {
                right = mid - 1;// Shrink the right border
            } else if(nums[mid] == target) {
                right = mid - 1;// Shrink the right border
            } else if(nums[mid] < target) {
                left = mid + 1; }}if(left >= nums.length || nums[left] ! = target)return -1;
        return left;
    }
    
    public int rightBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        while(left <= right) {
            mid = left + (right-left)/2;
            if(nums[mid] > target) {
                right = mid - 1;
            } else if(nums[mid] == target) {
                left = mid + 1;// Shrink the left border
            } else if(nums[mid] < target) {
                left = mid + 1; }}if (right < 0|| nums[right] ! = target)return  -1;
        returnright; }}Copy the code