# Find First and Last Position of a Number in a Sorted Array – Java Code

Given a sorted array which contains duplicate elements, Write a java code to find first and last position of a number in a sorted array. Given a number x, write a code to find it’s first and last index in an array.

For example –

Suppose the input array is arr[] : {1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13, 13} and the number to be searched is 11. Then the first index of 11 is 5 and last index is 8.

So, how to find the first and last index of an element in a sorted array? In this tutorial, i am going to discuss two approaches and their time complexity to solve this problem.

## Find First and Last Index of a Number in a Sorted Array

The first approach is to traverse an array to find the first and last index of a number.

i) Run a for loop from i = 0 to n-1
ii) Take two indexes first and last and assign initial value of -1 (first = -1 and last = -1 ).
iii) Assign a value to first index when we find the number first time in an array.
iv) Assign last index whenever we find the element. At last, print the first and last indexes.

The time complexity of this approach is O(n).

Can we reduce the time complexity? Yes, we can solve this problem in O(logn) time complexity using binary search.
If you are not familiar with the binary search algorithm then check my previous tutorial on binary search algorithm.

Subscribe Our Tutorials

Binary search in java

Binary search using recursion in java

## Find First and Last Position of a Number in a Sorted Array using Binary Search

The array is sorted, so we can use binary search algorithm to find first and last position of a number in an array. The time complexity of this approach is O(logn).

## Find First and Last Position of a Number in an Array using Binary Search : Video Tutorial 