Binary Search Rightmost and leftmost element Optimised ( i.e., with less lines )
Finding the right most occrued elemnt in the array and the left most occured elemnt in the array
Following is sample java code.
import java.util.*;
public class Main {
public static int LeftMost(int arr[] , int target)
{
int l=0;
int r=arr.length - 1;
while(l<=r)
{
int mid = l+(r-l)/2;
//if(arr[mid]==target)
// r = mid - 1;
// else
if(arr[mid]>=target) // here we will just remove the if because the same is repeating and added >= instead of >
r = mid -1;
else
l=mid+1;
}
// some of the edge cases WHEN THE TRGET IS NOT IN ARRAY
if( l > arr.length-1) // ( when target is bigger than the last element in the array )
return -1;
if(arr[l]!=target) // ( when the target is smaller that the first element of array )
return -1;
return l; // ( here we return the l for right most )
}
public static int RightMost(int arr[],int target)
{
int l=0;
int r=arr.length-1;
while(l<=r)
{
int mid = l + (r-l)/2;
// if(arr[mid]==target)
// l = mid + 1 ;
// else
if(arr[mid]>target) // here also we will just remove the if because the same is repeating
r = mid - 1;
else
l = mid + 1;
}
// some of the edge cases WHEN THE TRGET IS NOT IN ARRAY
if( r == -1) // ( when target is smaller than the last element in the array )
return -1;
if(arr[r]!=target) // ( when the target is bigger that the first element of array )
return -1;
return r; // ( here we return the r for right most )
}
public static void main(String[] args) {
int arr[]={1,3,3,3,3,3,4,5};
System.out.println("Left Most occured at index :"+ LeftMost(arr,3));
System.out.println("Right Most occured at index :"+ RightMost(arr,3));
}
}