Binary search is an algorithm that searches for a specific value in a sorted array by repeatedly dividing the search interval in half.
Here's an example implementation of binary search in Java:
public class BinarySearchExample { public static int binarySearch(int[] arr, int target) { int low = 0; int high = arr.length - 1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } public static void main(String[] args) { int[] arr = { 1, 3, 5, 7, 9 }; int target = 5; int result = binarySearch(arr, target); if (result == -1) { System.out.println("Target value not found in array"); } else { System.out.println("Target value found at index " + result); } } }
This program defines a class BinarySearchExample with a binarySearch method that takes an integer array arr and a target value target, and returns the index of the target value in the array if it is present, or -1 if it is not present.
The main method creates an example array arr and a target value target, and calls the binarySearch method with these arguments. It then checks the return value of the binarySearch method and prints a message indicating whether the target value was found or not.
The binarySearch method works by first setting the low and high boundaries of the search interval to the beginning and end of the array, respectively. It then repeatedly computes the midpoint of the search interval and compares the value at that index to the target value. If the value at the midpoint is equal to the target, the search is complete and the method returns the midpoint index. If the value at the midpoint is less than the target, the search interval is shifted to the right half of the array by setting the low boundary to the midpoint plus one. If the value at the midpoint is greater than the target, the search interval is shifted to the left half of the array by setting the high boundary to the midpoint minus one. The process repeats until the target value is found or the search interval is empty.