Home » Core Java » Binary Search Java Example Simranjit Singh has graduated from Computer Science Department of the Guru Nanak Dev University of Amritsar, Punjab, India. He also holds a Master degree in Software Engineering from the Birla Institute of Technology & Science of Pilani, Rajasthan, India. He works as a Senior Consultant in the e-commerce sector where he is mainly involved with projects based on Java and Big Data technologies.

# Binary Search Java Example

A popular searching algorithm in Java is the Binary Search algorithm. In this article, I will show you all about its implementation through examples.

## 1. Introduction

Algorithms like Searching and Sorting are the most popular algorithms in any programming language. They are the basis to understand the fundamentals of programming.

Binary Search in Java is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. It works only on a sorted set of elements. To use `binary search` on a collection, the collection must first be sorted.

When the `binary search` is used to perform operations on a sorted set, the number of iterations can always be reduced based on the value that is being searched.

You can also check this tutorial in the following video:

## 2. Implementing Binary Search Algorithm

Let’s take a look at the below pseudo code to understand it in a better way.

```Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched

Set low = 1
Set high = n

if high < low
EXIT: x does not exist.

set mid = low + ( high - low ) / 2

if A[mid]  x
set high = mid - 1

if A[mid] = x
EXIT: x found at location mid
end while

end procedure
```

Explanation:

Step 1: First, compare x with the middle element.

Step 2: If x matches with the middle element, then you have to return the mid index.

Step 3: Else, If x is greater than the mid element, then x can only lie in the right side half array after the mid element. Hence you recur the right half.

Step 4: Else, if (x is smaller) then recur for the left half.

## 3. Binary Search examples

Iterative implementation of Binary Search in Java programming language.

```// Java implementation of iterative Binary Search
public class BinarySearch {
// Returns index of x if it is present in arr[],
// else return -1
static int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;

// Check if x is present at mid
if (arr[m] == x)
return m;

// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;

// If x is smaller, ignore right half
else
r = m - 1;
}

// if we reach here, then element was
// not present
return -1;
}

// Driver method to test above
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at "
+ "index " + result);
}
}

```

There are two ways to do `binary search` in Java.

### 3.1. Arrays.binarysearch() works for arrays which can also be a primitive data type

A sortedArray and an int key, which is to be searched in the array of integers, are passed as arguments to the binarySearch method of the Java Arrays class.

```// Java program to demonstrate working of Arrays.
// binarySearch() in a sorted array.
import java.util.Arrays;

public class ArrayBinarySearch {
public static void main(String[] args)
{
int arr[] = { 10, 20, 15, 22, 35 };
Arrays.sort(arr);

int key = 22;
int res = Arrays.binarySearch(arr, key);
if (res >= 0)
System.out.println(key + " found at index = "
+ res);
else

key = 40;
res = Arrays.binarySearch(arr, key);
if (res >= 0)
System.out.println(key + " found at index = "
+ res);
else
}
}
```

### 3.2. Collections.binarysearch() works for object Collections like ArrayList and LinkedList

A sortedList & an Integer key, which is to be searched in the list of Integer objects, are passed as arguments to the binarySearch method of the Java Collections class.

```// Java program to demonstrate working of Collections.
// binarySearch()
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class CollectionBinarySearch
{
public static void main(String[] args)
{
List al = new ArrayList();

// 10 is present at index 3.
int key = 10;
int res = Collections.binarySearch(al, key);
if (res >= 0)
System.out.println(key + " found at index = "
+ res);
else

key = 15;
res = Collections.binarySearch(al, key);
if (res >= 0)
System.out.println(key + " found at index = "
+ res);
else
}
}
```

Complexities like O(1) and O(n) are simple to understand. O(1) means it requires constant time to perform operations like to reach an element in constant time as in case of dictionary and O(n) means, it depends on the value of n to perform operations such as searching an element in an array of n elements.

• Worst-case performance O(log n)
• Best-case performance O(1)
• Average performance O(log n)

A linear search scans one item at a time, without jumping to any item .

1. The worst-case complexity is O(n), sometimes known an O(n) search.
2. Time taken to search elements keep increasing as the number of elements is increased.

A binary search however, cut down your search to half as soon as you find middle of a sorted list.

1. The middle element is looked to check if it is greater than or less than the value to be searched.
2. Accordingly, the search is done to either half of the given list.

Differences:

• Input data needs to be sorted in Binary Search and not in Linear Search
• Linear search does the sequential access whereas Binary search access data randomly.
• The time complexity of linear search O(n), Binary search has time complexity O(log n).
• Linear search performs equality comparisons and Binary search performs ordering comparisons

You can download the full source code of this example here: Binary Search Java Example

# Do you want to know how to develop your skillset to become a Java Rockstar?

## Subscribe to our newsletter to start Rocking right now!

### and many more .... 