Find first and last position of element in sorted array.
Given a sorted array which contains duplicate elements. Write a code to find first and last position of a number in a sorted array.
OR
Find first and last occurrences of x in sorted array where x is a target value.
If a number is not found return -1.
For example –
Example 1 –
Input : {1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13, 13} , target = 11
Output: {5, 8}
The first index of 11 is 5 and last index is 8.
Example 2 –
Input: {1, 6, 7, 7, 8, 8, 9, 9}, target = 5
Output: {-1, -1}
The target value is not found.
NOTE – We have to solve this problem in O(logn) time complexity.
Before checking the solution, Let’s think for a moment how do you approach this problem? How we can efficiently find the first and last occurrences of x where x is the target element.
In this tutorial, i am going to discuss multiple approaches and their time and spaces complexities to solve this problem. At the end of this tutorial, I have shared the link to the video tutorial.
Find First and Last Occurrences of an Element in a Sorted Array – Linear Search
The simplest approach is to traverse an array and find the indexes of first and last occurrences of x where x is a target number.
Here are the following steps –
i) Run a loop from i = 0 to n-1 where n is the size of an array.
ii) Declare two variables firstIndex and lastIndex. Initialized with -1 (firstIndex = -1 and lastIndex = -1 ).
iii) When target number is found first time, Assigned a new value to firstIndex.
iv) For last occurrence of a target keep assigning the value to lastIndex till the number is equal to the target number.
After the complete traversal, print the first and last index of a target number.
The time complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
/** * Find first and last position of Element in Array */ public class FirstAndLastIndex { public static void main(String[] args) { //Input array int arr[] = { 1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13, 13 }; //Value to be searched int search = 11; int firstIndex = -1; int lastIndex = -1; //Run a loop from 0 to n-1 for (int i = 0; i < arr.length; i++) { //Assign only first time in firstIndex if (arr[i] == search && firstIndex == -1) { firstIndex = i; } //Assign value at last index if (arr[i] == search && firstIndex != -1) { lastIndex = i; } } System.out.println(" First index found at " + firstIndex); System.out.println(" Last index found at " + lastIndex); } } |
This is the simplest approach to solve this problem. In this approach, we have not used the sorted property of an array.
How we can improve our solution to solve this problem in O(logn) time complexity.
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.
Binary search using recursion in java
Programming questions on binary search
Find First and Last Position of Element in 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.
To solve this problem, We have to create two separate functions. The first function will find the first occurrence of an element in a sorted array. In second function we find the last occurrence of element in a sorted array.
The time complexity of this approach is O(logn).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
/** * Using binary search to find first and last index */ public class FirstAndLastPosition { //Finding first position of a number public static int findFirstPosition(int[] arr, int target) { int start = 0; int end = arr.length-1; int index = -1; while (start <= end) { int mid = (start + end) / 2; if (arr[mid] == target) { index = mid; end = mid - 1; } else if (arr[mid] > target) { end = mid -1; } else { start = mid+1; } } return index; } public static int findLastPosition(int[] arr, int target) { int start = 0; int end = arr.length - 1; int index = -1; while (start <= end) { int mid = (start + end) / 2; if (arr[mid]==target) { index= mid; start = mid+1; } else if (arr[mid] > target) { end = mid-1; } else { start = mid+1; } } return index; } public static void main(String[] args) { int arr[] = { 1, 4, 7, 8, 11, 11, 11, 11, 11, 13 }; int target = 11; int firstIndex = findFirstPosition(arr, target); int lastIndex = findLastPosition(arr, target); System.out.println("First position " + firstIndex); System.out.println("Last position " + lastIndex); } } |
Find First and Last Position of a Number in an Array using Binary Search : Video Tutorial
Find First and Last Position of Element in Sorted Array Video Tutorial
