Binary Search with java.lang.Arrays

In the realm of computer science, searching plays a vital role in various algorithms and applications. It's the process of finding a specific item within a collection of items. There are several search algorithms, each with its unique characteristics. Among them, binary search stands out as one of the most efficient methods, especially for larger datasets. In this article, we'll delve into the world of binary search, its advantages over linear search, and how Java's java.lang.Arrays#binarySearch method can be used to implement it effectively.

What is a Search algorithm?

Search algorithms are algorithms that are designed to find an element with a specific property within a collection of items. Whether it's finding a particular value in a database, locating a file on a computer, or searching for a word in a dictionary, search algorithms are fundamental to many computing tasks.

 

Types of Search

1.   Linear Search: It is also known as sequential search, where each element in the collection is checked one by one until the desired element is found or the end of the collection is reached. While it is simple to implement, linear search is inefficient, especially for larger datasets, as it has a time complexity of O(n), where n is the number of elements in the collection.

2.   Binary Search: Binary search is a more efficient search algorithm, particularly suited for sorted collections. It follows the principle of divide and conquer, where the collection is repeatedly divided into two halfs until the desired element is found. Binary search has a time complexity of O(log n), making it significantly faster than linear search for large datasets.

 

How Binary Search Improves Performance over Linear Search?

The primary advantage of binary search over linear search lies in its time complexity. Binary search operates by dividing the search space into two halfs at each step, drastically reducing the number of comparisons required, especially for large datasets. This logarithmic time complexity makes binary search much faster than linear search, particularly as the size of the dataset increases.

 

Let me explain it with an example with below dataset.

 

data: [2, 3, 5, 7, 8, 9, 10, 13, 14, 16, 19, 20, 24, 25, 32, 45]

elementToSearch: 25.

 

Start with the entire dataset.

Define the search range by setting the start index to 0 and the end index to the length of the dataset minus 1. Calculate the mid index as the average of start and end.

 

Dataset: [2, 3, 5, 7, 8, 9, 10, 13, 14, 16, 19, 20, 24, 25, 32, 45]

Element to Search: 25

start = 0, end = 15, mid = (0 + 15) / 2 = 7

 

Compare the element at index mid with the target element (25). In this case, the element at index mid is 13, which is less than the target element. Since the element at mid is less than the target element, all the elements that are leftside of the element 13 are always less than 25, so we update the start index to mid + 1, and start searching in right half of the middle element.

 

Dataset: [2, 3, 5, 7, 8, 9, 10, 13, 14, 16, 19, 20, 24, 25, 32, 45]

Element to Search: 25

start = 7 + 1 = 8, end = 15, mid = (8 + 15) / 2 = 11

 

Element at index 11 is 20, which is less than the target element. Let’s set the start index to mid + 1, and start searching in right half from the middle element.

 

Dataset: [2, 3, 5, 7, 8, 9, 10, 13, 14, 16, 19, 20, 24, 25, 32, 45]

Element to Search: 25

Start = 11 + 1 = 12, end = 15, mid = (12 + 15) / 2 = 13

 

Element at index 13 is 25, that’s it we got the element, and search ends here.

 

Pseudo code of Binary search using iteration

function binarySearch(array, target):
    left = 0
    right = length of array - 1
    
    while left <= right:
        mid = (left + right) / 2
        
        // If the middle element is the target, return its index
        if array[mid] == target:
            return mid
        
        // If the target is less than the middle element, search the left half
        else if target < array[mid]:
            right = mid - 1
        
        // If the target is greater than the middle element, search the right half
        else:
            left = mid + 1
    
    // If the target is not found, return -1
    return -1

 

Pseudo code of Binary search using recursion

function binarySearch(array, target, left, right):
    if left > right:
        return -1  // Target not found
    
    mid = (left + right) / 2
    
    if array[mid] == target:
        return mid  // Target found at index mid
    else if target < array[mid]:
        return binarySearch(array, target, left, mid - 1)  // Search left half
    else:
        return binarySearch(array, target, mid + 1, right)  // Search right half

Following table summarizes the number of comparison required by Binary search for a given dataset size.

 

Number of Elements	Number of comparison needed
2	log₂(2) = 1
4	log₂(4) = 2
8	log₂(8) = 3
16	log₂(16) = 4
32	log₂(32) = 5
64	log₂(64) = 6
128	log₂(128) = 7
256	log₂(256) = 8
512	log₂(512) = 9
1024	log₂(1024) = 10
2048	log₂(2048) = 11
4096	log₂(4096) = 12
8192	log₂(8192) = 13
16384	log₂(16384) = 14
32768	log₂(32768) = 15
65536	log₂(65536) = 16
131072	log₂(131072) = 17
262144	log₂(262144) = 18
524288	log₂(524288) = 19
1048576	log₂(1048576) = 20

 

You can observer from above table that, we can able to search an element in a million element just using 20 comparisons.

 

FAQs about Binary Search

1.   Does Binary Search Work Only on Sorted Data?

Yes, binary search requires the data to be sorted in ascending order. This is essential for the algorithm to function correctly, as it relies on comparing elements and narrowing down the search space based on their relative positions.

 

2.   What is the Time Complexity of Binary Search?

The time complexity of binary search is O(log n), where n is the number of elements in the collection. This logarithmic time complexity means that binary search scales efficiently with increasing dataset sizes, making it ideal for large collections.

 

‘java.lang.Arrays’ class provides below methods to search for an element using binary search.

static int binarySearch(byte[] a, byte key)
static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key)
static int binarySearch(char[] a, char key)
static int binarySearch(char[] a, int fromIndex, int toIndex, char key)
static int binarySearch(double[] a, double key)
static int binarySearch(double[] a, int fromIndex, int toIndex, double key)
static int binarySearch(float[] a, float key)
static int binarySearch(float[] a, int fromIndex, int toIndex, float key)
static int binarySearch(int[] a, int key)
static int binarySearch(int[] a, int fromIndex, int toIndex, int key)
static int binarySearch(long[] a, int fromIndex, int toIndex, long key)
static int binarySearch(long[] a, long key)
static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key)
static int binarySearch(Object[] a, Object key)
static int binarySearch(short[] a, int fromIndex, int toIndex, short key)
static int binarySearch(short[] a, short key)
static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

Above methods searches the given element in the array of values using the binary search algorithm. This method return the index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

 

Find the below working application.

BinarySearchDemo.java

package com.sample.app;

import java.util.Arrays;

public class BinarySearchDemo {

    public static void main(String args[]) {
        String[] primitiveTypes = new String[] { "boolean", "byte", "char", "double", "float", "int", "long", "short",
                "void" };

        String eleToSearch = "boolean";
        int index = Arrays.binarySearch(primitiveTypes, eleToSearch);
        if (index >= 0) {
            System.out.println(eleToSearch + " found at position " + index);
        } else {
            System.out.println(eleToSearch + " not found");
        }

        eleToSearch = "float";
        index = Arrays.binarySearch(primitiveTypes, eleToSearch);
        if (index >= 0) {
            System.out.println(eleToSearch + " found at position " + index);
        } else {
            System.out.println(eleToSearch + " not found");
        }

        eleToSearch = "Integer";
        index = Arrays.binarySearch(primitiveTypes, eleToSearch);
        if (index >= 0) {
            System.out.println(eleToSearch + " found at position " + index);
        } else {
            System.out.println(eleToSearch + " not found");
        }
    }

}

Output

boolean found at position 0
float found at position 4
Integer not found

 

Previous                                                 Next                                                 Home