Using Binary Search in Java
Tags: java, codenewbie, tutorial, 100daysofcode
Published: 2021-11-27 20:04:05

---
title: Using Binary Search in Java
published: true
description: Using Binary Search in Java
tags: Java, codenewbie, tutorial, 100daysofcode
//cover_image: https://direct_url_to_image.jpg
---
_Binary search_ is a [search algorithm](https://en.wikipedia.org/wiki/Binary_search_algorithm) that searches for an element, or _key_, by repeatedly dividing the array in half while it searches for the key. It is faster than [linear search](https://en.wikipedia.org/wiki/Linear_search), which searches each element of an array sequentially.

Java makes it easy to use binary search in your programs. The `java.util.Arrays` class provides several versions of the `binarySearch()` function that find different types of keys, using various options.

It is important to note that the binary search algorithm requires that you sort the array *before* using binary search. The Java `Arrays` class conveniently provides a `sort()` method that sorts an array in increasing order.

Here is a binary search example. First, import the `Arrays` class:

```bash
import java.util.Arrays;
```

Next, create a sample array named `arr`:

```bash
int[] arr = {10, 1, 3, 20, 99, 5, 8, 2, 4};
```

To sort the array in increasing order, call the `sort()` method on `arr`:

```bash
Arrays.sort(arr);
```

Let's output the array to verify that it is sorted:

```bash
System.out.println( Arrays.toString(arr) ); // [1, 2, 3, 4, 5, 8, 10, 20, 99]
```

Now that the array is sorted, we can use the `binarySearch()` function. This statement searches for the value `20` in the array:

```java
System.out.println( Arrays.binarySearch(arr, 20) ); // 7
```

The `binarySearch()` function returns the index of the key in the array if it finds it. In this case, the return value is `7`, since `20` is at position `7` of the array.

If the key is _not_ found in the array, the `binarySearch()` function returns a negative number that follows this formula:

```bash
(-(insertion point) - 1)
```

The _insertion point_ is the index of the first element that is greater than the key **or** the length of the array if all elements are less than the key.

Here is a binary search that fails:

```java
System.out.println( Arrays.binarySearch(arr, 7) ); // -6
```

In this example, the insertion point is `5`; the value `8` is the first element that is greater than the key `7`, and its index is `5`. With `5` as the insertion point value, the formula gives the return value `-(5) - 1` or `-6`.

Here is the complete program:

```java
import java.util.Arrays;

public class Example {
  public static void main(String[] args) {

    int[] arr = {10, 1, 3, 20, 99, 5, 8, 2, 4};

    Arrays.sort(arr);

    System.out.println( Arrays.toString(arr) );

    System.out.println( Arrays.binarySearch(arr, 20) ); // 7

    System.out.println( Arrays.binarySearch(arr, 7) ); // -6

  }
}
```

Remember to keep the array sorted if the array elements ever change. Just call the `Arrays.sort()` method on the array to sort it again.

Thanks for reading.

Follow me on Twitter [`@realEdwinTorres`](https://twitter.com/realEdwinTorres) for more programming tips. 😀