Core Java

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

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:

Binary Search Java Tutorial – 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
 
while x not found
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
            System.out.println(key + " Not found");

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

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();
        al.add(1);
        al.add(2);
        al.add(3);
        al.add(10);
        al.add(20);

        // 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
            System.out.println(key + " Not found");

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

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

6. Download the Source Code

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

Simranjit Singh

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.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button