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
Nothing listed.
5.1. vogella Java example code
If you need more assistance we offer Online Training and Onsite training as well as consulting