Sequential and binary search implemented in Java - Tutorial

1. Searching in collections

The following article will discuss the implementation of different search algorithms in Java for finding elements in a collections.
Searching in collection is done to answer the questions:

• Does the element exists in the collections
  
• Get the element from the collection
  
• Delete the element from the collection
  

Collection in this article is used in the broader sense and not in the strict Java sense. For example collection we are looking at my be array or lists.

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 a 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 http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html Mergesort. Binary search checks the element in the middle of the collection. If the search element smaller or greater then the found element then a sub-array is defined which is then search again. If the searched element is smaller then the found element then the sub-array is from the start of the array until the found element. If the searched element is larger then the found element then the sub-array is 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. Support this website

This tutorial is Open Content under the CC BY-NC-SA 3.0 DE license. Source code in this tutorial is distributed under the Eclipse Public License. See the vogella License page for details on the terms of reuse.
Writing and updating these tutorials is a lot of work. If this free community service was helpful, you can support the cause by giving a tip as well as reporting typos and factual errors.

4.1. Thank you