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 afor
loop, returns the found object, else returnsnull
.findItemViaStream
– it checks item sequentially in a list via aStream
, return the found object, else returnsnull
.
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.
You can download the full source code of this example here: Linear Search Java Example