In this post, you will learn to implement Binary Search Algorithm in Java Programming language. Let’s see “How to code a Java Program to implement Binary Search Algorithm?”
We will discuss two ways to implement Binary Search: Using Loops and Recursion
What is Binary Search?
Binary search is a “Divide and Conquer” based searching algorithm that searches data in the time complexity of O(log n).
Note: The given array must be sorted. The given binary search code is for an array with Ascending order
Now, let’s see the Java Program to implement Binary Search Algorithm.
Java Program to Implement Binary Search Algorithm
import java.util.*;
public class Main{
public static int binarySearch(int[] arr,int target, int start, int end){
while(start <= end){
int mid = (start + end)/2;
if(arr[mid] == target){
return mid;
} else if(target > arr[mid]){
start = mid + 1;
} else if(target < arr[mid]){
end = mid - 1;
}
}
//if element not present
return -1;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int[] arr = {1,2,4,5,8,9,11,22,23,28,32};
System.out.println("Enter the target number to search :");
int target = sc.nextInt();
int ans = binarySearch(arr,target,0,arr.length - 1);
if(ans == -1){
System.out.println("Element "+target+" is not present.");
} else{
System.out.println("Element "+target+" is present at "+ans+" index");
}
}
}
Output
Enter target element : 22
Element 22 is present at 7 indexHow Does This Program Work ?
In the given program we created a sorted array we wanted to search elements from. Then we took the input of the target element we want to search.
Then we created the binarySearch function which returns the index of the element if the element is present in O(log n) otherwise it returns -1.
We have created a binarySearch function with parameters given array, target element, starting index, ending index.
public static int binarySearch(int[] arr,int target, int start, int end){
while(start <= end){
int mid = (start + end)/2;
if(arr[mid] == target){
return mid;
} else if(target > arr[mid]){
start = mid + 1;
} else if(target < arr[mid]){
end = mid - 1;
}
}
return -1;
}In the above logic to implement the binary search, we created a while loop with a condition of start <= end.
Then we find the mid element by (start+end)/2, which can be further optimized to mid = start-(start-end) / 2 to avoid overflow.
- Now, if the element at index mid i.e. arr[mid] is equal to the target then we immediately return the mid.
- And if the element at index mid i.e. arr[mid] is smaller than the target, then we decrease our search space by half by assigning the start at mid + 1 i.e. start = mid +1;
- And if the element at index mid i.e. arr[mid] is greater than the target, then we decrease our search space by half by assigning the end at mid – 1 i.e. end = mid – 1;
Hence, by using this logic we achieve a time complexity of O(log n). This is Binary Search Algorithm in Java.
Similarly, we can also implement the Binary Search algorithm using recursion.
Java Program to implement Binary Search using Recursion
import java.util.*;
public class Main{
public static int binarySearch(int[] arr,int target, int start, int end){
if(start > end ) {
return -1;
}
int mid = (start + end)/2;
if(arr[mid] == target){
return mid;
} else if(target > arr[mid]){
return binarySearch(arr,target,mid+1,end);
} else if(target < arr[mid]){
return binarySearch(arr,target,start,mid-1);
}
return -1;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int[] arr = {1,2,4,5,8,9,11,22,23,28,32};
System.out.println("Enter the target number to search :");
int target = sc.nextInt();
int ans = binarySearch(arr,target,0,arr.length - 1);
if(ans == -1){
System.out.println("Element "+target+" is not present.");
} else{
System.out.println("Element "+target+" is present at "+ans+" index");
}
}
}
Output
Enter target element : 22
Element 22 is present at 7 index
Enter target element : 52
Element 52 is not present.How Does This Program Work ?
In this program instead of loop, we used recursion to implement the binary search algorithm.
If start > end then we return -1; i.e base case of the recursive function
if the element at index mid i.e. arr[mid] is equal to the target then we immediately return the mid.
And if the element at index mid i.e. arr[mid] is smaller than the target, then we decrease our search space by half by calling binarySearch( arr, target, mid+1, end );
And if the element at index mid i.e. arr[mid] is greater than the target, then we decrease our search space by half by calling binarySearch( arr, target, start, mid-1 );
This was the Java Program to implement Binary Search using Recursion.
Conclusion
I hope after going through this post, you understand how to code Java Program to implement Binary Search Algorithm. We also discussed How to code Java Program to implement Binary Search using Recursion
If you have any doubt regarding the topic, feel free to contact us in the Comment Section. We will be delighted to help you.
Also Read: