# Binary search in java

Let’s learn binary search in java.

## Binary search in java

Binary search is the process of searching key element from sorted array.

binary search algorithm java

As you can see in the below image we have a sorted array of size 5.

Now given an array, we have to find whether key element exist in the given array or not. If key element exist in the above array, then find the index position where it exists.

Before that we have to declare three variables start, middle element and end.

Here to find middle element

middleelement = (start + end) / 2;

Let’s say key element to search is equal to 20 and we want to find whether 20 exists in the array.

Clearly, if key element is equal to the middle element, our search is over. Because we have found key element in the array.

If key element is less than the middle element, then it lies before the middle element and we can discard middle element and all the elements after middle element.

And if key element is greater than the middle then it lies after the middle element so we can discard all the elements before the middle element.

Initially our search space was whole array. Now we compare it with the middle element which is 30.

Key element is less than 30. So it should exist somewhere before 30. We discard all the elements after 30 and 30 as well. We need to search key element only between index 0 and 1.

This kind of search where we reduce the search space into half at each comparison is called binary search.

We are able to reduce the search space into half only because the array is sorted. Here array must be sorted to perform binary search. Here’s binary search program in java.

### Binary

```// binary search java code
public class BinarySearchExample
{
public static void binarySearch(int[] arrNumbers, int start, int end, int keyElement)
{
int middle = (start + end) / 2;
while(start <= end)
{
if(arrNumbers[middle] < keyElement)
{
start = middle + 1;
}
else if(arrNumbers[middle] == keyElement)
{
System.out.println("Element found at index: " + middle);
break;
}
else
{
end = middle - 1;
}
middle = (start + end) / 2;
}
if(start > end)
{
}
}
public static void main(String[] args)
{
int[] arrNumbers = {14,15,16,17,18};
int keyElement = 16;
int end = arrNumbers.length - 1;
binarySearch(arrNumbers, 0, end, keyElement);
}
}

```

Output:

Element found at index: 2

Binary search using recursion in java

Here’s binary search using recursion (recursive).

```public class BinarySearchRecursion
{
int binaryRecursion(int[] arrNum, int left, int right, int m)
{
if(right >= left)
{
int mid = left + (right - left) / 2;
// checking if element is present in middle
if(arrNum[mid] == m)
return mid;
// checking if element is small than middle element
if(arrNum[mid] > m)
return binaryRecursion(arrNum, left, mid - 1, m);
// if not element can only be present in right
return binaryRecursion(arrNum, mid + 1, right, m);
}
// we come out of the loop if not present in array
return -1;
}
public static void main(String[] args)
{
BinarySearchRecursion bsr = new BinarySearchRecursion();
int[] arrBinary = {1,4,6,14,32};
int num = arrBinary.length;
int a = 14;
int result = bsr.binaryRecursion(arrBinary, 0, num - 1, a);
if(result == -1)
{
System.out.println("Sorry!!Element is not present");
}
else
{
System.out.println("Element found at index " + result);
}
}
}

```

Output:

Element found at index 3

Binary search using iterative approach

Here’s the code.

```public class BinaryIterativeDemo
{
// here code returns index of variable y in the array else return -1
int searchBinary(int[] arrNum, int y)
{
int left = 0, right = arrNum.length - 1;
while(left <= right)
{
int m = left + (right - left) / 2;
// checking if variable y is present at middle
if(arrNum[m] == y)
return m;
// check if variable y is greater, neglect left
if(arrNum[m] < y)
left = m + 1;
// check if variable y is smaller, neglect right
else
right = m - 1;
}
// we come out of the loop if not present in array
return -1;
}
public static void main(String[] args)
{
BinaryIterativeDemo bs = new BinaryIterativeDemo();
int[] arrBinary = {1, 4, 6, 14, 32};
int x = 32;
int output = bs.searchBinary(arrBinary, x);
if(output == -1)
{
System.out.println("Sorry!!Element not present");
}
else
{
System.out.println("Element found at index " + output);
}
}
}

```

Output:

Element found at index 4

Binary search time complexity:

T(n) = T(n/2) + c

Binary search example in java using Arrays.binarySearch()

We can also execute above example using Arrays.binarySearch() method.

```import java.util.Arrays;
public class UsingArraysBinarySearch
{
public static void main(String[] args)
{
int[] arrNumbers = {15,16,17,18,19};
int keyElement = 17;
int output = Arrays.binarySearch(arrNumbers, keyElement);
if(output < 0)
{
}
else
{
System.out.println("Element found at index: " + output);
}
}
}

```

Output:

Element found at index: 2

Also read – for each loop in java