Common Algorithms
Linear Search
When searching through a small collection like a shopping cart or a list of recent notifications, you need a simple and reliable method. Linear search checks each item one by one, making it useful for unsorted data and small datasets where more complex algorithms are unnecessary.
Basic Implementation
Linear search compares each element with a target until it finds a match or reaches the end.
Basic.java
public class Basic {
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // found - return index
}
}
return -1; // not found
}
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 9, 3};
int target = ;
System.out.println("Array: " + java.util.Arrays.toString(numbers));
System.out.println("Search " + target + ": index " + linearSearch(numbers, target));
}
}
public class Basic {
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // found - return index
}
}
return -1; // not found
}
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 9, 3};
int target = ;
System.out.println("Array: " + java.util.Arrays.toString(numbers));
System.out.println("Search " + target + ": index " + linearSearch(numbers, target));
}
}
public class Basic {
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // found - return index
}
}
return -1; // not found
}
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 9, 3};
int target = ;
System.out.println("Array: " + java.util.Arrays.toString(numbers));
System.out.println("Search " + target + ": index " + linearSearch(numbers, target));
}
}
Linear Search
A sequential search algorithm that examines each element in order until finding the target or exhausting all elements.
Searching Strings
The same algorithm works for object values when the equality check matches the data type.
Strings.java
public class Strings {
static int searchString(String[] arr, String target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i].equals(target)) {
return i;
}
}
return -1;
}
static int searchCaseInsensitive(String[] arr, String target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i].equalsIgnoreCase(target)) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
String[] fruits = {"apple", "banana", "cherry", "date", "elderberry"};
System.out.println("Fruits: " + java.util.Arrays.toString(fruits));
System.out.println("Search 'cherry': " + searchString(fruits, "cherry"));
System.out.println("Search 'grape': " + searchString(fruits, "grape"));
System.out.println("\nCase-insensitive:");
System.out.println("Search 'BANANA': " + searchCaseInsensitive(fruits, "BANANA"));
System.out.println("Search 'Apple': " + searchCaseInsensitive(fruits, "Apple"));
}
}
Counting Occurrences
Linear search can track work done while it scans.
Count.java
public class Count {
static class SearchResult {
int index;
int comparisons;
SearchResult(int index, int comparisons) {
this.index = index;
this.comparisons = comparisons;
}
}
static SearchResult linearSearchCounted(int[] arr, int target) {
int comparisons = 0;
for (int i = 0; i < arr.length; i++) {
comparisons++;
if (arr[i] == target) {
return new SearchResult(i, comparisons);
}
}
return new SearchResult(-1, comparisons);
}
public static void main(String[] args) {
int[] numbers = {10, 20, 30, 40, 50};
var result1 = linearSearchCounted(numbers, 10); // first element
System.out.println("Search 10: index=" + result1.index +
", comparisons=" + result1.comparisons);
var result2 = linearSearchCounted(numbers, 50); // last element
System.out.println("Search 50: index=" + result2.index +
", comparisons=" + result2.comparisons);
var result3 = linearSearchCounted(numbers, 99); // not found
System.out.println("Search 99: index=" + result3.index +
", comparisons=" + result3.comparisons);
}
}
Finding All Matches
Instead of stopping at the first match, keep scanning and collect every matching index.
FindAll.java
import java.util.ArrayList;
import java.util.List;
public class FindAll {
static List<Integer> findAll(int[] arr, int target) {
List<Integer> indices = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
indices.add(i);
}
}
return indices;
}
public static void main(String[] args) {
int[] numbers = {3, 7, 3, 9, 3, 1, 3};
System.out.println("Array: " + java.util.Arrays.toString(numbers));
System.out.println("All 3's at: " + findAll(numbers, 3));
System.out.println("All 9's at: " + findAll(numbers, 9));
System.out.println("All 5's at: " + findAll(numbers, 5));
}
}
Predicate Search
Predicate.java
public class Predicate {
interface IntPredicate {
boolean test(int value);
}
static int findFirst(int[] arr, IntPredicate condition) {
for (int i = 0; i < arr.length; i++) {
if (condition.test(arr[i])) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] numbers = {3, 7, 12, 5, 18, 9};
System.out.println("Array: " + java.util.Arrays.toString(numbers));
int evenIdx = findFirst(numbers, x -> x % 2 == 0);
System.out.println("First even at index: " + evenIdx);
int largeIdx = findFirst(numbers, x -> x > 10);
System.out.println("First > 10 at index: " + largeIdx);
int negIdx = findFirst(numbers, x -> x < 0);
System.out.println("First negative at index: " + negIdx);
}
}
Predicate Search
Instead of searching for one value, search for the first element that satisfies a condition.
Practical Use
Small inventories, recent items, and unsorted collections are natural places for linear search.
Practical.java
public class Practical {
record Product(String id, String name, double price) {}
static Product findById(Product[] inventory, String targetId) {
for (Product p : inventory) {
if (p.id().equals(targetId)) {
return p;
}
}
return null; // not found
}
static Product findCheapest(Product[] inventory) {
if (inventory.length == 0) return null;
Product cheapest = inventory[0];
for (int i = 1; i < inventory.length; i++) {
if (inventory[i].price() < cheapest.price()) {
cheapest = inventory[i];
}
}
return cheapest;
}
public static void main(String[] args) {
Product[] inventory = {
new Product("A101", "Widget", 9.99),
new Product("B202", "Gadget", 19.99),
new Product("C303", "Doohickey", 4.99),
new Product("D404", "Thingamajig", 14.99)
};
System.out.println("Inventory:");
for (Product p : inventory) {
System.out.println(" " + p);
}
System.out.println("\nSearch by ID:");
Product found = findById(inventory, "C303");
System.out.println("Found: " + found);
Product notFound = findById(inventory, "X999");
System.out.println("Not found: " + notFound);
System.out.println("\nCheapest product:");
System.out.println(findCheapest(inventory));
}
}
Exercise: Practical.java
Implement a linear search that returns the last occurrence of a target value