Write a function in Java to implement a binary search algorithm on a sorted array of integers. The function should take in the array and the target integer as input, and return the index of the target integer in the array. If the target integer is not found in the array, the function should return -1.
Java Function for Binary Search Algorithm
A binary search algorithm is an efficient way to search for a particular element in a sorted array. Here's a Java function that can implement a binary search algorithm on a sorted array of integers.
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
This function takes in two parameters: an array of sorted integers and the target integer that we want to search. The function returns the index of the target integer in the array, or -1 if the target integer is not found.
The function works by dividing the array in half repeatedly until the target integer is found or until the search space is empty. At each iteration, the function calculates the midpoint of the search space and compares the target integer with the element at the midpoint. Depending on the comparison, the search space is reduced to the left or right half, until the target integer is found or until the search space is empty.
Using this binary search algorithm can significantly reduce the time complexity of searching for an element in a sorted array from O(n) to O(log n).
References: