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

Given a sorted array which contains duplicate elements, we have to 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 number to searched is 11 then the first index of 11 is 5 and last index is 8.

Find first and last index of an element in an array

Find first and last index of an element in an array

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 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 for this approach is O(n).

 

Can we do 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

Get Latest Updates on Facebook

Binary search in java

Binary search using recursion in java

Find First and Last Position of a Number in a Sorted Array

Find First and Last Position of a Number in a Sorted Array

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 the 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

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.
Tagged , , . Bookmark the permalink.