Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one. Here is a simple Java program that implements binary search on an array of integers. This example assumes the array is sorted in ascending order.
public class BinarySearchExample {
public static void main(String[] args) {
int[] sortedArray = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}; // A sorted array
int target = 18; // The number to find
int resultIndex = binarySearch(sortedArray, target);
if (resultIndex == -1) {
System.out.println(target + " was not found in the array.");
} else {
System.out.println(target + " was found at index " + resultIndex + ".");
}
}
public static int binarySearch(int[] array, int toFind) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] == toFind) {
return mid; // Target found
} else if (array[mid] < toFind) {
low = mid + 1; // Search in the right half
} else {
high = mid - 1; // Search in the left half
}
}
return -1; // Target not found
}
}
```
How it Works:
- The search begins with the entire array.
- The array is halved by calculating the middle index.
- If the target value matches the middle element, the search is complete.
- If the target value is less than the middle element, the search continues on the left half of the array.
- If the target value is greater than the middle element, the search continues on the right half of the array.
- This process repeats until the target is found or the search space is reduced to zero.