Back to: Java Tutorials
Binary Search
Binary search is an efficient algorithm used to search for a specific value in a sorted list or array of elements. This algorithm works by repeatedly dividing the search interval in half until the target value is found.
To illustrate how binary search works, let’s consider a sorted array of integers [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]. Suppose we want to find the index of the element 11 in the array using binary search.
The first step is to calculate the middle index of the array, which is (0 + 9) / 2 = 4. We compare the middle element (9) with the target element (11) and find that 11 is greater than 9. Therefore, we only need to search the right half of the array [11, 13, 15, 17, 19].
Next, we calculate the middle index of the right half of the array, which is (4 + 9) / 2 = 6. We compare the middle element (13) with the target element (11) and find that 11 is less than 13. Therefore, we only need to search the left half of the right half of the array [11].
We calculate the middle index of the left half of the right half of the array, which is (4 + 5) / 2 = 4.5. Since the middle index is not an integer, we round it down to 4. We compare the middle element (11) with the target element (11) and find a match. Therefore, we have found the index of the target element, which is 5.
Binary Search Code Example using Java
Here’s an example of binary search in Java:
public class BinarySearch {
public static int search(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int target = 7;
int index = search(arr, target);
if (index == -1) {
System.out.println("Target not found in the array");
} else {
System.out.println("Target found at index " + index);
}
}
}
This code uses the binary search algorithm to search for a target value in a sorted array. It takes an array arr and a target value target as inputs, and returns the index of the target value if it is found in the array. If the target value is not found, it returns -1.
The search method uses a while loop to repeatedly divide the search space in half until the target value is found or the search space is exhausted. It maintains two pointers, left and right, that define the bounds of the search space. It calculates the middle index mid using integer division, and compares the value at arr[mid] to the target value. If the value at arr[mid] is equal to the target value, it returns mid. If the value at arr[mid] is less than the target value, it updates left to mid + 1 to search the right half of the search space. If the value at arr[mid] is greater than the target value, it updates right to mid - 1 to search the left half of the search space.
The main method provides an example of how to use the search method to find the index of the target value 7 in the array {1, 3, 5, 7, 9}. If the index returned by search is -1, it prints a message indicating that the target value was not found. Otherwise, it prints a message indicating the index at which the target value was found.
Also, see the example code JavaExamples_NoteArena in our GitHub repository. See complete examples in our GitHub repositories.
Follow us on social media
Follow Author