Java Program to Implement Binary Search Algorithm
What is a Searching?
In Java, searching refers to the process of finding an element or a group of elements in a data structure, such as an array or a list. There are several algorithms and techniques that can be used to search for an element in a data structure, including linear search, binary search, and hash search.
In this Article, we will write a program to implement binary search in java.
What is Binary Search in Java?
Binary search is an efficient algorithm for finding an element in a sorted list of items. It works by repeatedly dividing the list in half until the element is found or it is clear that the element is not in the list.
Algorithm of Binary Search:
The basic steps to perform Binary Search are:
- First, set the lower and upper bounds of the search area to the beginning and end of the array, respectively.
- Calculate the middle index of the search area by taking the average of the lower and upper bounds.
- Compare the element at the middle index to the target element. If they are equal, the search is complete and the index of the middle element is returned.
- If the element at the middle index is less than the target element, set the lower bound of the search area to be one index above the middle index.
- If the element at the middle index is greater than the target element, set the upper bound of the search area to be one index below the middle index.
- Repeat steps 2 through 5 until the target element is found or the search area becomes empty. If the search area becomes empty, the target element is not present in the array and the search is unsuccessful.
Pseudo Code for Binary Search :
public static int binarySearch(int[] arr, int Prep) {
int low = 0;
int high = arr.length - 1;
int mid;
while (low <= high) {
mid = low + (high - low) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
Explanation:
This implementation takes an array of integers and a target integer as input, and returns the index of the target integer if it is found in the array, or -1 if it is not found.
To use this method, you can call it like this:
int[] arr = {10, 20, 30, 40, 50};
int index = binarySearch(arr, 30); // index will be 2
Example 1:
import java.util.*;
public class Main{
public static int binarySearch(int[] array, int target){
int left = 0;
int right = array.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (array[middle] == target) {
return middle;
} else if (array[middle] < target){
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
public static void main(String[] args){
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 5;
int result = binarySearch(array, target);
System.out.println("The Given Target is Present at : " + result);
}
}
Output: The Given Target is Present at : 4
Explanation:
This implementation searches for the target value in a sorted array by repeatedly dividing the search interval in half. If the target value is found, the function returns its index in the array. If the target value is not found, the function returns -1.
The search begins with the left and right indices pointing to the beginning and end of the array, respectively. The middle index is then calculated as the average of the left and right indices. If the value at the middle index is equal to the target value, the search is complete and the middle index is returned. If the value at the middle index is less than the target value, the left index is updated to be one position to the right of the middle index. If the value at the middle index is greater than the target value, the right index is updated to be one position to the left of the middle index. The search continues until the target value is found or the left index becomes greater than the right index, indicating that the target value is not present in the array.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment