Java Accepted - two paths: find first target and find last target


  • 1
    D

    Inspired by Make mid biased to right to find the last index of target.

    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] ret = {-1, -1};
            int n = nums.length;
            if (n == 0) return ret;
            int i = 0, j = n-1;
            while (i < j) {
                int mid = (i + j)/2;
                if (nums[mid] == target)
                    j = mid;
                else if (nums[mid] < target)
                    i = mid+1;
                else
                    j = mid;
            }
            if (nums[i] == target)
                ret[0] = i;
            else
                return ret;
            j = n-1; // i starts from the first position of target
            while (i < j) {
                int mid = (i + j + 1) / 2;  // make mid biased to right, symmetric to the first while loop.
                if (nums[mid] == target)
                    i = mid;
                else if (nums[mid] > target)
                    j = mid - 1;
                // (nums[mid] < target) --> not possible
            }
            ret[1] = j;
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.