Binary search:
Binary search is an efficient algorithm for an element in a sorted array. It is a classic example of a divide-and-conquer algorithm, and it significantly reduces the search time by repeatedly dividing the search interval in half.
In this article, we will discuss the implementation of the Binary Search algorithm in Java.
First, let's understand how the Binary Search algorithm works. It takes an array and a target element as input and returns the index of the target element in the array. If the element is not found in the array, it returns -1.
The algorithm begins by comparing the target element with the middle element of the array. If the target element is equal to the middle element, the search is successful, and the index of the middle element is returned. If the target element is less than the middle element, the search is continued on the left half of the array. If the target element is greater than the middle element, the search is continued on the right half of the array. This process is repeated until the target element is found or the search interval is reduced to zero.
 |
| Binary search algorithm implementation in java |
Binary search is a searching algorithm that can search first-er, then Sequential search. It's executed in O (log N) time.
A binary search can
only be performed if the list is in sorted order.
Now, let's implement the Binary Search algorithm in Java. Here is the code:
import java.util.Scanner;
public class BinarySearchTry {
public static void main(String[] args) {
int n, key, b, j, mid, t;
Scanner s = new Scanner(System.in);
System.out.println("Enter number of element: ");
n = s.nextInt();
int[] ar = new int[n];
for(j = 0; j<n ; j++){
System.out.println("No "+ (j+1) + " = ");
ar[j] = s.nextInt();
}
System.out.println("Enter element to search: ");
key = s.nextInt();
b = 1;
t = n;
do{
mid = (b+t)/2;
if(key<ar[mid]){
t = mid - 1;
}
else if(key>ar[mid]){
b = mid+1;
}
}
while(key != ar[mid] && b<= t);
if(key == ar[mid]){
System.out.println("Found !!!");
}
else{
System.out.println("Not Found !!!");
}
}
}code-box
The binarySearch method takes two parameters, an integer array arr, and an integer target. It returns the index of the target element in the array. If the element is not found in the array, it returns -1.
The left variable is set to 0, representing the array's leftmost index. The right variable is set to arr.length - 1, which means the rightmost index of the array.
The while loop runs as long as the left is less than or equal to the right. The mid variable is calculated as the average of left and right indices. The target element returns to the index mid if it is found at mid.
If the target element is greater than the element at mid, the left is set to mid + 1. This means the search will continue on the array's right half. If the target element is less than the element at mid, the right is set to mid-1. This means the search will continue on the array's left half.
If the loop completes without finding the target element, it returns -1.
int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int index = binarySearch(arr, 23);
if (index != -1) {
System.out.println("Element found at index " + index);
} else {
System.out.println("Element not found");
}code-box
The output of this code will be:
An element found at index 5 code-box
As expected, the Binary Search algorithm successfully found the target element 23 at index 5.
Conclusion
The Binary Search algorithm efficiently searches for an element in a sorted array. The implementation in Java is straightforward to understand. Using this algorithm can significantly reduce the time complexity of searching for an element in a large array.