Home Tutorials Training Consulting Books Company Contact us


Get more...

Search Algorithms in Java. This article describes the implementation of different search algorithms for searching elements in collections. Currently sequential search and binary search are described.

1. Searching in Collections

The Java programming language offers a variety of search algorithms that are both fast and efficient for locating elements within a collection.

This article explores the implementation of various standard search algorithms in Java, focusing on their functionality rather than relying on existing standard implementations.

When searching in collections, several key questions arise:

  • Does the element exist within the collection?

  • How can I retrieve the element from the collection?

  • How can I remove the element from the collection?

In this context, the term "collection" is used broadly and does not strictly adhere to Java’s Collection framework. For example, a collection may include arrays or lists.

2. Implementation

For the upcoming implementations, we will need a project named com.vogella.algorithms.search. To utilize JUnit for testing, create a Maven project with the necessary dependencies and add the following to your pom.xml file:

In this project, we will create different packages and implement software tests for various search algorithms.

3. Sequential Search

3.1. Overview

Sequential search is the simplest search approach. Given a collection, it involves examining each element in the collection until the desired element is found or the end of the collection is reached.

3.2. Implementation

Implementing a sequential search is straightforward. Create a Java project named com.vogella.algorithms.search.sequential, along with a package that shares the same name. Then, create the following program.

package com.vogella.algorithms.search.sequential;

public class SequentialSearch {
    public static boolean contains(int[] a, int b) {
        for (int i : a) {
            if (i == b) {
                return true;
            }
        }
        return false;
    }
}

3.3. Test

You can use the following JUnit test to validate the functionality of your contains method. For more information on JUnit, please refer to the [JUnit Tutorial](https://www.vogella.com/tutorials/JUnit/article.html).

3.4. Test

You can use the following JUnit 5 test to validate the functionality of your contains method. For more information on JUnit 5, please refer to the [JUnit 5 Tutorial](https://www.vogella.com/tutorials/JUnit/article.html).

package com.vogella.algorithms.search.sequential;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

import org.junit.jupiter.api.Test;

public class SequentialSearchTest {

    @Test
    public void testContains() {
        int[] a = {1, 2, 3, 4, 5, 19, 17, 7};
        assertTrue(SequentialSearch.contains(a, 17));
        assertTrue(SequentialSearch.contains(a, 1));
        assertTrue(SequentialSearch.contains(a, 2));
        assertTrue(SequentialSearch.contains(a, 3));
        assertTrue(SequentialSearch.contains(a, 4));
        assertFalse(SequentialSearch.contains(a, 10));
    }

}

3.5. Complexity Analysis

The sequential search algorithm has an average and worst-case runtime complexity of O(N). For an introduction to complexity analysis, see [Complexity Analysis](https://www.vogella.com/tutorials/ComplexityAnalysis/article.html).

4. Binary Search

4.1. Overview

Binary search is a highly efficient algorithm that locates an element in a sorted collection. To perform a binary search, the collection must first be sorted using algorithms like [Quicksort](https://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html) or [Mergesort](https://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html).

The algorithm works by checking the element in the middle of the collection. If the target element is equal to the middle element, the search is complete. If the target element is smaller than the middle element, the search continues in the left sub-array (from the start of the array to the middle element). If the target element is larger, the search continues in the right sub-array (from the middle element to the end of the array). This process repeats until the target element is found or the search space is exhausted.

4.2. Implementation

To implement binary search, create a Java project named com.vogella.algorithms.search.binary and a package with the same name.

Here is the program that performs the binary search:

package com.vogella.algorithms.search.binary;

public class BinarySearch {
    public static boolean contains(int[] a, int b) {
        if (a.length == 0) {
            return false;
        }
        int low = 0;
        int high = a.length - 1;

        while (low <= high) {
            int middle = (low + high) / 2;
            if (b > a[middle]) {
                low = middle + 1;
            } else if (b < a[middle]) {
                high = middle - 1;
            } else { // The element has been found
                return true;
            }
        }
        return false; // Element not found
    }
}

4.3. Test

You can use the following JUnit 5 test to validate the functionality of your contains method. For more information on JUnit 5, please refer to the [JUnit 5 Tutorial](https://www.vogella.com/tutorials/JUnit/article.html).

package com.vogella.algorithms.search.binary;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

import org.junit.jupiter.api.Test;

public class BinarySearchTest {

    @Test
    public void testContains() {
        int[] a = {1, 2, 3, 4, 5, 7, 17, 19}; // Sorted array
        assertTrue(BinarySearch.contains(a, 1));
        assertTrue(BinarySearch.contains(a, 2));
        assertTrue(BinarySearch.contains(a, 3));
        assertTrue(BinarySearch.contains(a, 4));
        assertFalse(BinarySearch.contains(a, 10)); // Element not in array
        assertTrue(BinarySearch.contains(a, 17));
    }
}

4.4. Complexity Analysis

Binary search significantly reduces the search space with each iteration, resulting in a time complexity of O(log N). For more information on complexity analysis, please see the [Complexity Analysis Tutorial](https://www.vogella.com/tutorials/ComplexityAnalysis/article.html).

5. Links and Literature

Legal Privacy Policy Change consent