## What is Binary Search?

Binary search is used to find a target value in an array. The goal is to find the target value with a minimum number of attempts or iterations. The binary search algorithm operates on sorted arrays. Search iterations are performed on the array by repeatedly dividing the search interval in half. If the search value is less than the value in the middle of the search interval, discard the upper half and continue with the lower half. Iterate this process until the search value is found or no interval is left.

## How to implement binary search

Let's take the below array and implement the binary search algorithm to find a given value. To make it practical, let's begin with an unsorted array.

```
int array[] = {30,1,40,50,31,2,8,3,6,5};
```

The first step is to sort the array to make it binary sort ready. This is crucial since we use the indexes of the array elements during the sorting process to compare the actual value contained in the index. The below code uses java to sort the array, but the logic is applicable for any programming language.

```
Arrays.sort(array);
```

The sorted array will look like `{1,2,3,5,6,8,30,31,40,50}`

Now, this array is ready to be binary searched. Let's pick a random number to search: 40. At the end of this tutorial, we will do the full code implementation of binary search. With our implementation, a search for random value 40 would look like this.

`binarySearch(array,40);`

### Step 1: Find the index of the middle position

Our sorted array length is 10. Since we use the index of the position, the first index becomes 0, and the last index is array length -1. Using these numbers, we can calculate the middle position as:

`start`

= 0

`end = array.length-1`

= 9

`middle = ((start + end) / 2) = int 9 / int 2`

= 4

This leads us to position 4 in the array. Position 4 holds the value 6, which is smaller than the value we are looking for. Now we know 40 lies between index 5 and 9. Therefore, we can discard the portion of the array lower than index 5 (lower half) and continue our search with the upper half where the index is 5 or greater.

### Step 2: Eliminate and continue

Now our focus is between index 5 and 9. Let's eliminate the remaining portion of the array. Our start position becomes middle + 1 and the end position remains the end of the array.

Since 40 > 6 at `array[middle]`

`start = middle + 1`

= 5

`middle = (5 + 9) / 2`

= 7

Index 7 is our new middle. This position holds 31, which is still smaller than our search value of 40.

Now we can eliminate the array index lower than 8. Our search value lies on or above index position 8.

Since 40 > 31 at `array[middle]`

`start = middle + 1`

= 8

`middle = (8 + 9) / 2`

= 8

Now our middle is 8 and we find what we are looking for. At this point, it is not necessary to continue with the search, we can simply return the position and exit the function.

The source code for this example is listed below.

```
private static int binarySearch(int[] array, int val)
{
Arrays.sort(array);
int start = 0;
int end = array.length-1;
int middle;
while(start <= end)
{
middle = (start + end) / 2;
if(array[middle] == val)
return middle;
if(array[middle] < val)
{
start = middle +1;
}
else
{
end = middle -1;
}
}
return -1;
}
```