Home Tutorials Training Consulting Products Books Company Donate Contact us









NOW Hiring

Quick links

Share

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

1. Searching in collections

The following article will analyze the implementation of different search algorithms in Java for finding elements in a collection.

Searching in collections is done to answer the following questions:

  • Does the element exists in a collection?

  • How to get the element from a collection?

  • How to delete the element from a collection?

"Collection" in this article is used in the broader sense and not in the strict Java sense. For example a collection may be an array or a list.

2. Sequential Search

2.1. Overview

Sequential search is the simplest approach. Given a collection you try every element in the collection until you have found the element or until you reach the end of the collection.

2.2. Implementation

Sequential Search is extremely easy to implement. Create the Java project "de.vogella.algorithms.search.sequential" and a package with the same name. Create the following program.

package de.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;
    }
}

2.3. Test

You can use the following JUnit test to validate your sort method. To learn about JUnit please see JUnit Tutorial.

package de.vogella.algorithms.search.sequential;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.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));
    }

}

2.4. Complexity Analysis

See Complexity Analysis for an introduction to the topic.

Sequential search has an average and worst-case runtime of O(N).

3. Binary Search

3.1. Overview

Binary search requires that the collection is already sorted. For example by Quicksort or Mergesort. Binary search checks the element in the middle of the collection. If the search element is smaller or greater than the found element, then a sub-array is defined which is then searched again. If the searched element is smaller than the found element, then the sub-array is searched from the start of the array until the found element. If the searched element is larger than the found element, then the sub-array is searched from the found element until the end of the array. Once the searched element is found or the collection is empty then the search is over.

3.2. Implementation

Create the Java project "de.vogella.algorithms.search.binary" and a package with the same name.

Create the following program.

package de.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;
    }
}

3.3. Test

You can use the following JUnit test to validate your sort method. To learn about JUnit please see JUnit Tutorial.

package de.vogella.algorithms.search.binary;


import org.junit.Test;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class BinarySearchTest {

    @Test
    public void testContains() {
        int[]a = {1, 2, 3, 4, 5, 7, 17,  19 };
//      assertTrue(BinarySearch.contains(a, 17));
        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));
    }

}

3.4. Complexity Analysis

See Complexity Analysis for an introduction to the topic.

Binary search cuts the search space in each iteration into half and has therefore O(lg N) runtime behavior.

4. About this website

5. Links and Literature

Not listed yet.

5.3. vogella GmbH training and consulting support

TRAINING SERVICE & SUPPORT

The vogella company provides comprehensive training and education services from experts in the areas of Eclipse RCP, Android, Git, Java, Gradle and Spring. We offer both public and inhouse training. Whichever course you decide to take, you are guaranteed to experience what many before you refer to as “The best IT class I have ever attended”.

The vogella company offers expert consulting services, development support and coaching. Our customers range from Fortune 100 corporations to individual developers.

Copyright © 2012-2017 vogella GmbH. Free use of the software examples is granted under the terms of the EPL License. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.

See Licence.