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