1. First and Last occurrence of x

1. First and Last occurrence of x

Problem link :- click here

package program;

public class Searching__1
{

	/*
	 	Given a sorted array arr[] containing n elements with possibly duplicates, 
	 	the task is to find indices of first and last element x in the given array
	 			n = 9                 x = 5
	 		arr[] = {1, 3, 5, 5, 5, 5, 5, 67, 123, 125}
	 	 output :     2      5
	 	 
	 	 lets do it using binary search
	 */
	
	static void firstAndLastOccurrence(int arr[], int n, int x)
	{
		int low, high, mid;
		
		low = 0;
		high = n-1;
		
		//this is to find the first occurrence 
		int first;             // we are giving first a maximum value
		while(low <= high)
		{
			mid = (low + high)/2;
			
			//if we get the arr[mid] == x        then we have to check if there is one 
			//more element that is == x       to the left as we are finding first occurrence
			
			if(arr[mid] >= x)
			{
				//first = mid;
				high = mid - 1;
			}
			else
				low = mid + 1;
		}
		first = low;
		
		//this is to find the last occurrence of the element x
		int last;
		low = 0;
		high = n - 1;
		while(low <= high)
		{
			mid = (low + high)/2;
			
			if(arr[mid] <= x)
			{
				//last = mid;
				low = mid + 1;
			}
			else
				high = mid - 1;
		}
		last = high;
		
		System.out.println("First and last occurrence is : " + first + "    " + last);
	}
	
	public static void main(String[] args)
	{
		int arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125};
		int x = 3;
		firstAndLastOccurrence(arr, arr.length, x);
	}

}

Time complexity :- O(log(n))
Space complexity :- O(1)