Binary search is a searching algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the value of the target is less than the middle element of the array, then the search continues on the lower half of the array; if the target value is greater, the search continues on the upper half. This process continues until the target value is found or the search interval is empty.
Here’s a step-by-step explanation of how binary search works:
1. Initialize two pointers, `low` and `high`, which represent the indices of the first and last elements of the array, respectively.
2. Calculate the middle index of the current search interval using the formula: `mid = (low + high) / 2`.
3. Compare the target value with the middle element of the array.
– If the target value matches the middle element, return the index of the middle element.
– If the target value is less than the middle element, set `high = mid – 1` to search in the lower half of the array.
– If the target value is greater than the middle element, set `low = mid + 1` to search in the upper half of the array.
4. Repeat steps 2 and 3 until the target value is found or the search interval becomes empty (`low > high`).
If the target value is not found, binary search returns -1 to indicate that the value is not present in the array.
Here’s a simple implementation of binary search in Java:
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17};
int target = 13;
int index = binarySearch(arr, target);
if (index != -1) {
System.out.println("Element found at index " + index);
} else {
System.out.println("Element not found");
}
}
}
In this implementation, the `binarySearch` method takes an array (`arr`) and a target value (`target`) as parameters and returns the index of the target value in the array using binary search. The `main` method demonstrates how to use this method by searching for a target value in a sorted array.