One solution: one is two binary search , the other worst case O(n)


  • 0
    K
    public class Solution {
        public int[] searchRange(int[] nums, int target) {
           // find the far left one first (same problem will be find first target index in a sorted array which allow duplicate)
           int[] res = new int[]{-1,-1};
           if(nums == null || nums.length == 0) {
               return res;
           }
           // find far left duplicate one
           int i = 0; int j = nums.length -1;
           while(i < j) { // if we make i = j to be while loop i will always be j if j is not target
               int mid = i + (j-i) /2;
               int temp = nums[mid];
               if (temp >= target) {
                   j = mid; // beacuse we do not need to skip those
               }else {
                   i = mid + 1;
               }
           }
           if (nums[i] == target) {
               res[0] = i;
           }else {
               return res;
           }
           
           // find the far right duplicate one
           j = nums.length -1;
           while (i < j) { // if we make i = j to be while loop i will always be j if j is not target
               int mid = i + (j-i+1) /2 ; // bias to right in order the situation--> [3,2,2,2,2] target = 2 beacuse we make
               int temp = nums[mid];
               if (temp > target) {
                   j = mid -1;
               }else {
                   i = mid; // if we do not biase to right -- > unlike other bianry search we do i = mid + 1--> will result in infinte loop
               }
           }
           res[1] = i;
           return res;
           
           /*
           Solution 2 : worst case O(n)
           
           */
            // int[] res = new int[2];
            // if(nums == null || nums.length == 0) {
            //     return res;
            // }
            
            // int left = 0;
            // int right = nums.length -1;
            // while(left <= right) {
            //     int mid = left + (right-left) /2;
            //     int temp = nums[mid];
                
            //     if(temp < target) {
            //         left = mid + 1;
            //     }else if(temp>target) {
            //         right = mid-1;
            //     }else {
            //         // should have a better solution in this part when we find the target --> all 8 target 8 --> 
            //         int leftIndex = mid;
            //         int rightIndex = mid;
            //         while(leftIndex -1 >= 0 && nums[leftIndex-1] == target) {
            //             leftIndex--;
            //         }
            //         while(rightIndex + 1 < nums.length && nums[rightIndex +1] == target) {
            //             rightIndex++;
            //         }
            //         res[0] = leftIndex;
            //         res[1] = rightIndex;
            //         return res;
            //     }
            // }
            
            // res[0] = -1;
            // res[1] = -1;
            // return res;
        }
    }```

Log in to reply
 

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