# Java Binary Search Interactive and Recursive

Harshit Jindal Jan 30, 2023 Feb 24, 2021
Note
If you want to understand Binary Search in detail then refer to the binary search algorithm article.

## Iterative Binary Search Algorithm

Let us assume that we have an unsorted array `A[]` containing `n` elements, and we want to find an element `X`.

• ##### While `lo` < `hi`:
• Set `mid` = `lo + (hi - lo)/2`.
• If `A[mid] == X` , we have found the element return the index `mid`.
• If `A[mid] < X` ,then discard the left half of elements and set `lo` as `mid+1`.
• Else if `A[mid] > X`, then discard the right half of elements and set `hi` as `mid-1`.
• ##### Element is not found, so return `-1`.
``````class BinarySearch {
int binarySearch(int arr[], int x)
{
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] < x)
lo = mid + 1;

else
hi = mid - 1;
}
return -1;
}

public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
int x = 5;
int position = ob.binarySearch(arr, x);
if (position == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index: " + position);
}
}
``````

Output:

``````Element found at index: 4
``````

## Recursive Binary Search Algorithm

Let us assume that we have an unsorted array `A[]` containing `n` elements, and we want to find an element `X`.

• ##### Else if `X` is greater than `mid`, search the upper half of the array by recursively calling `binarysearch(arr, mid+1, hi)`.
``````class BinarySearch {
int binarySearch(int arr[], int lo, int hi, int x) {
if (hi >= lo && lo < arr.length - 1) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, lo, mid - 1, x);
return binarySearch(arr, mid + 1, hi, x);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
int x = 2;
int position = ob.binarySearch(arr, 0, n - 1, x);
if (position == -1)
else
System.out.println("Element found at index: " + position);
}
}
``````

Output:

``````Element found at index: 1
``````

## Java Internal `Arrays.binarySearch()` Overview

Java provides us with a ready to use function `Arrays.binarySearch()` so that we don’t have to implement the function ourselves. It is a very simple to use and efficiently implemented method and it is not prone to errors.

### Syntax

``````public static int binarySearch(T arr, T key )
``````

`T` can be any of the following: `int`, `float`, `short`, `long`, `byte`, `char`, `double`, and even a user-defined `Object` as well.

Just like our implemented binary search, it also requires the array to be sorted otherwise the results are undefined. It searches the array using the binary search algorithm and finds the index of the target element. If there are multiple occurrences of the target element then it can return the index of any one of them.

### Parameters

`Arr` The input array
`Key` The target element we are searching for.

### Return

If it finds the target element then it returns its index. Otherwise, it returns `beg - 1` where `beg` is the starting index of the array search space.

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

class BinarySearchExample{
public static void main(String args[]){
int arr[] = {1,2,3,4,5};
int key = 2;
int result = Arrays.binarySearch(arr,key);
if (result < 0)
``````Element is found at index: 1