*Binary search* is a 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, 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:

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

Next, create a sample array named `arr`

:

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

To sort the array in increasing order, call the `sort()`

method on `arr`

:

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

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

```
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:

```
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:

```
(-(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:

```
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:

```
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`

for more programming tips. 😀

## Discussion (0)