Find First and Last Index Occurrence of given target from Java Array using Binary Search
Problem Description :
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Example 1 :
Input: nums = [5, 7, 7, 8, 8, 8, 10], target = 8 Output: [3, 5]
Example 2 :
Input: nums = [5, 7, 7, 8, 8, 8, 10], target = 6 Output: [-1, -1]
We can solve this problem using brute force approach but it will take more time than binary search. So lets see binary search approach.
Solution 1 : Finding First and Last Position of Element in Array.
import java.util.Scanner;
public class FindFirstAndLastPosition {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter array size : ");
int size = sc.nextInt();
int[] array = new int[size];
// Taking user inputs
System.out.println("Enter array elements :");
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt();
}
System.out.println("Enter target : ");
int target = sc.nextInt();
int[] result = new int[2];
result[0] = searchFirstElement(array, target);
result[1] = searchLastElement(array, target);
System.out.println("["+result[0]+", "+result[1]+"]");
}
private static int searchFirstElement(int[] nums, int target) {
int index = -1;
if (nums.length == 0) {
return index;
}
int start = 0;
int end = nums.length-1;
while (start <= end) {
int mid = (end + start) / 2;
if (nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
if (nums[mid] == target) {
index = mid;
}
}
return index;
}
private static int searchLastElement(int[] nums, int target) {
int index = -1;
if (nums.length == 0) {
return index;
}
int start = 0;
int end = nums.length-1;
while (start <= end) {
int mid = (end + start) / 2;
if (nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
if (nums[mid] == target) {
index = mid;
}
}
return index;
}
}
Output :
Enter array size :
6
Enter array elements :
1 2 3 8 8 10
Enter target :
8
[3 , 4]
------------------------------
Enter array size :
10
Enter array elements :
1 2 3 5 6 8 10 11 18 20
Enter target :
4
[-1, -1]
Solution Explanation :
- Here we are using two methods, searchFirstElement for finding first and searchLastElement for finding last elements in given array. In both method, Binary search is used.
- In searchFirstElement method,
- We have to search till first element until current array element < target for finding first target.
- In searchLastElement method,
- We have to search till last element until current array element > target for finding last given target.
- At last return index from both methods.
Comments
Post a Comment