How to find the first occurrence using binary search in Java
Tarun TelangIntroduction
A binary search is an algorithm that searches for an element in a sorted array.
Refer to the following shots to learn more about Binary Search:
In this shot, we will modify the binary search algorithm to return the first occurrence of an integer in an array of integers sorted in ascending order.
Algorithm
In binary search, once we encounter the search target, we stop searching and return the middle index as the index of the search target. If the search ends with an empty half (left > right), then we terminate the search, returning “element is not found.”
In order to get the first occurrence, even after encountering the search target, we keep continuing the search for the target element on the left half until we reduce our search space to a single element (left = right).
The search is terminated in the following situations:
- If the target element is not present.
- Your current search space is reduced to a single element with the first occurrence of the search target.
Implementation using Java
Below is the Java code to implement the logic described above. You may run this to see it return the first occurrence of the search target for various test cases:
public class Main {
public static int getFirstOccurence(int[] array, int target){
// Return not found if array is emtpy
if (array == null || array.length == 0)
return -1;
// Intializing left and right positions
// of the search space
int left = 0;
int right = array.length - 1;
// Searches until you have atleast two elements
// in your search space
while(left < right) {
// Prevents integer overflow
int mid = left + (right - left)/2;
// if middle element is equal to search target,
if(array[mid] == target) {
// discard search space to the right of mid.
right = mid;
} else {
// discard search space from left to mid
left = mid + 1;
}
}
// after while loop, left will be equal to right
// i.e. you have only one element in search space
// return not found if its no equal to search target
// else return its index as first index.
return (array[left] == target) ? left : -1;
}
public static void main(String[] args) {
// empty array
int[] test = {};
// array with odd length
int[] test0 = {0, 0, 1, 1, 2, 3};
// array with single element containing search target
int[] test1 = {1};
// array with single element not containing search target
int[] test2 = {0};
// array with even length
int[] test3 = {0, 0, 2, 2, 2, 3};
// array containing search target at the end
int[] test4 = {0, 0, 0, 0, 3};
// array not containing search target
int[] test5 = {0, 1, 1, 2, 2};
System.out.println(getFirstOccurence(test, 1));
System.out.println(getFirstOccurence(test0, 1));
System.out.println(getFirstOccurence(test1, 1));
System.out.println(getFirstOccurence(test2, 2));
System.out.println(getFirstOccurence(test3, 2));
System.out.println(getFirstOccurence(test4, 3));
System.out.println(getFirstOccurence(test5, 3));
}
}Next Steps
To further strengthen your understanding, try implementing the code to return the last occurrence of the target element using a similar approach.
RELATED TAGS
CONTRIBUTOR
Tarun TelangView all Courses
