Linear Search Java Example

1. Introduction

Linear search is a computer algorithm which finds an element from an array sequentially. The time complexity is O(n) in the worst case – meaning the element is the last element of the array or not in the array. The time complexity is O(1) in the best case – meaning the element is the first element of the array. It’s useful when the array is small or not ordered.

In this example, I will demonstrate the following with a Maven project.

• How to code the linear search
• How JDK ArrayList implements the linear search
• When to use the linear search

2. Technologies Used

The example code in this article was built and run using:

• Java 11
• Maven 3.3.9
• Eclipse Oxygen
• Junit 4.12

3. Maven Project

3.1 Dependencies

I will include Junit in the pom.xml.

pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0"
	xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
	<modelVersion>4.0.0</modelVersion>
	<groupId>jcg.zheng.demo</groupId>
	<artifactId>java-linear-search-demo</artifactId>
	<version>0.0.1-SNAPSHOT</version>
	<build>
		<sourceDirectory>src</sourceDirectory>
		<plugins>
			<plugin>
				<artifactId>maven-compiler-plugin</artifactId>
				<version>3.8.0</version>
				<configuration>
					<release>11</release>
				</configuration>
			</plugin>
		</plugins>
	</build>
	<dependencies>
		<dependency>
			<groupId>junit</groupId>
			<artifactId>junit</artifactId>
			<version>4.12</version>
		</dependency>
	</dependencies>
</project>

3.2 Demo POJO

I will create a DemoPOJO which has equals method.

DemoPOJO.java

package jcg.zheng.demo.search;

public class DemoPOJO {

	private int id;

	private String name;

	public DemoPOJO(int id, String name) {
		super();
		this.name = name;
		this.id = id;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		DemoPOJO other = (DemoPOJO) obj;
		if (id != other.id)
			return false;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}

	public int getId() {
		return id;
	}

	public String getName() {
		return name;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + id;
		result = prime * result + ((name == null) ? 0 : name.hashCode());
		return result;
	}

	public void setId(int id) {
		this.id = id;
	}

	public void setName(String name) {
		this.name = name;
	}

}

3.3 Linear Search

I will createLinearSearch which has two methods:

• findItem – it checks item sequentially in a list via a for loop, returns the found object, else returns null.
• findItemViaStream – it checks item sequentially in a list via a Stream, return the found object, else returns null.

LinearSearch.java

package jcg.zheng.demo.search;

import java.util.List;

public class LinearSearch<T> {

	public T findItem(List<T> elements, T searchingItem) {
		for (T item : elements) {
			if (item.equals(searchingItem)) {
				return item;
			}
		}
		return null;
	}

	public T findItemViaStream(List<T> elements, T searchingItem) {
		return elements.stream().filter(customer -> searchingItem.equals(customer)).findAny().orElse(null);
	}
}

3.4 JDK ArrayList Index

I will show the ArrayList‘s implementation for the indexOf method which checks the item sequentially via a for loop.

ArrayList.indexOf.java

 @Override
        public int indexOf(Object o) {
            E[] a = this.a;
            if (o == null) {
                for (int i = 0; i < a.length; i++)
                    if (a[i] == null)
                        return i;
            } else {
                for (int i = 0; i < a.length; i++)
                    if (o.equals(a[i]))
                        return i;
            }
            return -1;
        }

3.5 Binary Search

I will create aBinarySearch which searches an item from an ordered array in a faster way. The time complexity is O(log n).

BinarySearch.java

package jcg.zheng.demo.search;

public class BinarySearch {

	public int findItemIndex(int elements[], int left, int right, int searchItem) {
		if (right >= left) {
			int mid = left + (right - left) / 2;

			if (elements[mid] == searchItem)
				return mid;

			if (elements[mid] > searchItem)
				return findItemIndex(elements, left, mid - 1, searchItem);

			return findItemIndex(elements, mid + 1, right, searchItem);
		}

		return -1;
	}

}

4. JUnit Test

I will demonstrate the linear search and binary search with several Junit test classes.

4.1 Linear Search Integer

I will create LinearSearch_IntegerTest.

LinearSearch_IntegerTest.java

package jcg.zheng.demo.search;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import org.junit.Before;
import org.junit.Test;

public class LinearSearch_IntegerTest {

	private List<Integer> elements;
	private LinearSearch<Integer> searchInt;

	@Test
	public void linearSearch_Integer() {
		Integer found = searchInt.findItem(elements, 20);
		assertNotNull(found);
		assertEquals(20, found.intValue());
	}

	@Test
	public void linearSearch_Stream_Integer() {
		Integer found = searchInt.findItemViaStream(elements, 20);
		assertNotNull(found);
		assertEquals(20, found.intValue());
	}

	@Before
	public void setup() {
		searchInt = new LinearSearch<>();
		elements = IntStream.iterate(10, x -> x + 10).limit(25).boxed().collect(Collectors.toList());
	}

}

4.2 Linear Search String

I will create LinearSearch_StringTest.

LinearSearch_StringTest.java

package jcg.zheng.demo.search;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;

import java.util.Arrays;
import java.util.List;

import org.junit.Before;
import org.junit.Test;

public class LinearSearch_StringTest {

	private List<String> elements;
	 
	private LinearSearch<String> searchInt;

	@Test
	public void linearSearch_Stream_String() {
		String found = searchInt.findItemViaStream(elements, "Mary");
		assertNotNull(found);
		assertEquals("Mary", found);
	}

	@Test
	public void linearSearch_String() {
		String found = searchInt.findItem(elements, "Mary");
		assertNotNull(found);
		assertEquals("Mary", found);
	}

	@Before
	public void setup() {
		searchInt = new LinearSearch<>();
		elements = Arrays.asList("Hello", "Mary", "How", "Are", "You");
	}

}

4.3 Linear Search POJO

I will create LinearSearch_POJOTest.

LinearSearch_POJOTest.java

package jcg.zheng.demo.search;

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

import java.util.ArrayList;
import java.util.List;

import org.junit.Before;
import org.junit.Test;

public class LinearSearch_POJOTest {

	private List<DemoPOJO> elements;
	private LinearSearch<DemoPOJO> searchPojo;

	@Test
	public void linearSearch_POJO() {
		DemoPOJO found = searchPojo.findItem(elements, new DemoPOJO(1, "Mary"));
		assertNotNull(found);
		assertTrue(found.equals(new DemoPOJO(1, "Mary")));
	}

	@Test
	public void linearSearch_Stream_POJO() {
		DemoPOJO found = searchPojo.findItemViaStream(elements, new DemoPOJO(1, "Mary"));
		assertNotNull(found);
		assertTrue(found.equals(new DemoPOJO(1, "Mary")));
	}

	@Before
	public void setup() {
		searchPojo = new LinearSearch<>();
		elements = new ArrayList<>();
		elements.add(new DemoPOJO(1, "Mary"));
		elements.add(new DemoPOJO(2, "Zheng"));
		elements.add(new DemoPOJO(3, "Alex"));

	}
}

4.4 Binary Search

I will create BinarySearchTest.

BinarySearchTest.java

package jcg.zheng.demo.search;

import static org.junit.Assert.*;

import org.junit.Test;

public class BinarySearchTest {

	private int arr[] = { 2, 3, 4, 10, 40 };
	private BinarySearch testClass = new BinarySearch();

	@Test
	public void search_item_found() {
		int itemIndex = testClass.findItemIndex(arr, 0, arr.length - 1, 10);
		assertEquals(10, arr[itemIndex]);
	}

	@Test
	public void search_item_not_found() {
		int itemIndex = testClass.findItemIndex(arr, 0, arr.length - 1, 60);
		assertEquals(-1, itemIndex);
	}

}

4.5 Run Tests

Execute the mvn test command and capture the output here.

Output

-------------------------------------------------------
 T E S T S
-------------------------------------------------------
Running jcg.zheng.demo.search.BinarySearchTest
Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.1 sec
Running jcg.zheng.demo.search.LinearSearch_IntegerTest
Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0 sec
Running jcg.zheng.demo.search.LinearSearch_POJOTest
Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0 sec
Running jcg.zheng.demo.search.LinearSearch_StringTest
Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0 sec

Results :

Tests run: 8, Failures: 0, Errors: 0, Skipped: 0

5. Linear Search Java Example – Summary

In this article, I created several Java classes to demonstrate how to implement a linear search. I also tested the search for an Integer, String, and DemoPOJO object. The time complexity of linear searching is O(n). When searching an item from a sorted list, the binary search has an O(log n) complexity.

6. Download the Source Code

This tutorial consists of a Maven project which includes Java classes to implement a linear search and binary search algorithms.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

and many more ....

I agree to the Terms and Privacy Policy

Sign up

Thank you!

We will contact you soon.