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

Convert multidimensional arrays to a string in Java

The Arrays.deepToString() method is a utility method provided in the java.util package in Java. It's used to generate a string representation of nested arrays.

 

When you pass a multidimensional array to Arrays.deepToString(), If an element e is an array of a primitive type, it is converted to a string as by invoking the appropriate overloading of Arrays.toString(e). If an element e is an array, then deepToString() is recursively called on those arrays until all elements are converted into their string representations.

 

DeepToStringDemo.java

package com.sample.app;

import java.util.Arrays;

public class DeepToStringDemo {
	
	public static void main(String[] args) {
		
		int[][] matrix1 = {
				{1, 2, 3}, 
				{4, 5, 6}, 
				{7, 8, 9}
		};
		String matrixString = Arrays.deepToString(matrix1);
		System.out.println("matrix1 : " + matrixString);
		
		int[][][] matrix2 = {
				{
					{1, 2, 3}, 
					{4, 5, 6}, 
					{7, 8, 9}
				},
				
				{
					{10, 11, 12}, 
					{13, 14, 15}, 
					{16, 17, 18}
				}
				
				
		};
		 matrixString = Arrays.deepToString(matrix2);
		System.out.println("matrix2 : " + matrixString);

	}

}

Output

matrix1 : [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
matrix2 : [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[10, 11, 12], [13, 14, 15], [16, 17, 18]]]

Previous                                                 Next                                                 Home

Concatenates the byte arrays in Java

Following snippet concatenates the byte arrays in Java.

public static byte[] concat(byte[]... byteArrays) {

	try {
		ByteArrayOutputStream baos = new ByteArrayOutputStream();

		for (byte[] byteArray : byteArrays) {

			if (byteArray == null) {
				continue;
			}

			baos.write(byteArray);
		}
		return baos.toByteArray();

	} catch (IOException e) {
		throw new IllegalStateException(e.getMessage(), e);
	}
}

Above snippet defines a method ‘concat’ that combines multiple byte arrays into a single byte array. It uses a ByteArrayOutputStream to store the concatenated byte arrays. The method checks for null byte arrays and skips them. For non-null byte arrays, it writes their content to the ByteArrayOutputStream. After processing all input byte arrays, the content of the ByteArrayOutputStream is converted into a single byte array, which is then returned.

 

Find the below working application.

 

ByteArrayConcatenation.java

package com.sample.app;

import java.io.ByteArrayOutputStream;
import java.io.IOException;

public class ByteArrayConcatenation {

	public static byte[] concat(byte[]... byteArrays) {

		try {
			ByteArrayOutputStream baos = new ByteArrayOutputStream();

			for (byte[] byteArray : byteArrays) {

				if (byteArray == null) {
					continue;
				}

				baos.write(byteArray);
			}
			return baos.toByteArray();

		} catch (IOException e) {
			throw new IllegalStateException(e.getMessage(), e);
		}
	}

	public static void main(String[] args) {
		byte[] arr1 = { 2, 3, 5, 7 };
		byte[] arr2 = { 23, 25, 27, 29 };
		byte[] arr3 = { 33, 35, 37, 39 };

		byte[] concatenatedArray = concat(arr1, arr2, arr3);
		
		System.out.println("Elements in the concatenated array are : ");
		for(byte b : concatenatedArray) {
			System.out.println(b);
		}

	}

}

Output

Elements in the concatenated array are : 
2
3
5
7
23
25
27
29
33
35
37
39

You may like

Interview Questions

Array programs in Java

Get the string representation of array by given delimiter in Java

Get an iterator from array in Java

Get reverse iterator for the given array in Java

Convert primitive array to wrapper array in Java

Convert a wrapper array to primitive array in Java

Convert a wrapper array to primitive array in Java

Write a program to convert the wrapper array to primitive array in Java. For example, for the Integer[] array, you should return int[].

 

Step 1: Write a function that return a primitive type equivalent to the given wrapper type.

private static final Map<Class<?>, Class<?>> WRAPPER_TO_PRIMITIVE;

static {
	WRAPPER_TO_PRIMITIVE = new LinkedHashMap<>();

	WRAPPER_TO_PRIMITIVE.put(Byte.class, byte.class);
	WRAPPER_TO_PRIMITIVE.put(Short.class, short.class);
	WRAPPER_TO_PRIMITIVE.put(Integer.class, int.class);
	WRAPPER_TO_PRIMITIVE.put(Long.class, long.class);
	WRAPPER_TO_PRIMITIVE.put(Float.class, float.class);
	WRAPPER_TO_PRIMITIVE.put(Double.class, double.class);
	WRAPPER_TO_PRIMITIVE.put(Boolean.class, boolean.class);
	WRAPPER_TO_PRIMITIVE.put(Character.class, char.class);
}

public static Class<?> getPrimitiveType(final Class<?> wrapperType) {
	final Class<?> primitiveType = WRAPPER_TO_PRIMITIVE.get(wrapperType);

	if (primitiveType == null) {
		throw new IllegalArgumentException("Given type is not a wrapper type");
	}

	return primitiveType;
}

Step 2: Get the component type of wrapper array.

Class<?> wrapperArrayClazz = wrapperArray.getClass();
Class<?> wrapperArrayComponentType = wrapperArrayClazz.getComponentType();

Step 3: Find the equivalent primitive type from the wrapper array component type.

Class<?> primitiveType = getPrimitiveType(wrapperArrayComponentType);

Step 4: Define primitive array and copy the elements one by one.

int length = Array.getLength(wrapperArray);
Object primitiveArray = Array.newInstance(primitiveType, length);
for (int i = 0; i < length; i++) {
	Object ele = Array.get(wrapperArray, i);
	Array.set(primitiveArray, i, ele);
}

Find the below working application.

 

ArrayWrapperToPrimitiveDemo.java

package com.sample.app.arrays;

import java.lang.reflect.Array;
import java.util.LinkedHashMap;
import java.util.Map;

public class ArrayWrapperToPrimitiveDemo {

	private static final Map<Class<?>, Class<?>> WRAPPER_TO_PRIMITIVE;

	static {
		WRAPPER_TO_PRIMITIVE = new LinkedHashMap<>();

		WRAPPER_TO_PRIMITIVE.put(Byte.class, byte.class);
		WRAPPER_TO_PRIMITIVE.put(Short.class, short.class);
		WRAPPER_TO_PRIMITIVE.put(Integer.class, int.class);
		WRAPPER_TO_PRIMITIVE.put(Long.class, long.class);
		WRAPPER_TO_PRIMITIVE.put(Float.class, float.class);
		WRAPPER_TO_PRIMITIVE.put(Double.class, double.class);
		WRAPPER_TO_PRIMITIVE.put(Boolean.class, boolean.class);
		WRAPPER_TO_PRIMITIVE.put(Character.class, char.class);
	}

	public static Class<?> getPrimitiveType(final Class<?> wrapperType) {
		final Class<?> primitiveType = WRAPPER_TO_PRIMITIVE.get(wrapperType);

		if (primitiveType == null) {
			throw new IllegalArgumentException("Given type is not a wrapper type");
		}

		return primitiveType;
	}

	public static Object toPrimitiveArray(final Object wrapperArray) {

		if (wrapperArray == null) {
			throw new IllegalArgumentException("Wrapper array cannot be null");
		}

		final Class<?> wrapperArrayClazz = wrapperArray.getClass();
		if (!wrapperArrayClazz.isArray()) {
			throw new IllegalArgumentException("Given input is not an array");
		}

		final Class<?> wrapperArrayComponentType = wrapperArrayClazz.getComponentType();
		final Class<?> primitiveType = getPrimitiveType(wrapperArrayComponentType);
		final int length = Array.getLength(wrapperArray);

		final Object primitiveArray = Array.newInstance(primitiveType, length);
		for (int i = 0; i < length; i++) {
			final Object ele = Array.get(wrapperArray, i);
			Array.set(primitiveArray, i, ele);
		}
		return primitiveArray;
	}

	public static void main(String[] args) {
		Integer[] primes = new Integer[] { 2, 3, 5, 7, 11 };

		int[] primesPrimitiveArray = (int[]) toPrimitiveArray(primes);

		for (int i : primesPrimitiveArray) {
			System.out.println(i);
		}
	}
}

Output

2
3
5
7
11

You may like

Interview Questions

Array programs in Java

Generic method to concatenate two arrays in Java

Get the string representation of array by given delimiter in Java

Get an iterator from array in Java

Get reverse iterator for the given array in Java

Convert primitive array to wrapper array in Java