Find first and last position of element in sorted array

Problem:

Given a sorted integer array find the first and last position of given target element

For example,

If given array is

[ 1,3,6,6,7,9]

and target is 6

Then output is

[2,3]

which represents the first and last index position of the element 6

For the same input if the target is 8

Then the output should be

[-1,-1]

Since the element is not present in the input.

Find a solution in O(log n ) time.

Try out the solution here:

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/

Solution:

Finding a solution of O(n) time complexity is fairly straightforward.

You just scan through the array from left and note down the first and last occurrence.

But to find an O(logn) solution we need a different approach.

Note that the given array is sorted.

So we can do a binary search of the target element.

Start from the middle of the array.

Check if the middle element is equal to target.

If yes , scan left and right to find the boundary of this element.

That will give us the required output.

If middle element is not equal to target then

Search left if it is greater than target

Search right if it is less than target

Also make sure the target is present in the array

This can be done by checking the current element and previous element.

If the target lies between these two and not equal to any of them then it is not present in the array.

So return the default result [-1,-1]

Here is the code :

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
    int[]  result = new int[2] ;
        
        
        
        int half = nums.length/2;
        
    
        
        
        while(half >=0 && half < nums.length){
            
            

       if(nums[half] == target){
  
                
        while(half -1 >= 0 && nums[half-1] == target){

           half--;

         }
                 
        

            result[0]= half;
       
                 
            
        while(half + 1 <= nums.length -1 

&& nums[half + 1] == target){

           half++;

         }
                 
        

             result[1]= half;

       return result;


                 
}else if(half - 1 >=0 
&& nums[half-1] < target 
&& nums[half] > target){

                 
                 return new int[]{-1,-1};
}
            
            
else if(nums[half] > target){

  half--;

}else{

 half++;

}

        }
        
        
        return new int[]{-1,-1};
        
    }
}

Time complexity:

Time complexity is O( log n) since we branch either left or right each time and the solution space gets halved

Space complexity:

We are not using any extra space so space complexity is O(1)

That’s it!