Linear Search is a simple search algorithm that scans the array sequentially and compares each element with the key (target value). If the key is found, it returns the index; otherwise, it returns -1.
This article shows you how the Linear search algorithm works with two examples to demonstrate the concept of Linear Search while catering to different use cases.
How Linear Search Works?
- Start at the first element of the array.
- Compare each element with the key.
- If a match is found, return the index of the element.
- If the end of the array is reached without finding the key, return
-1.
1. Linear Search Program in Java (Basic example)
This program example demonstrates a straightforward Linear Search on a 1D array of integers.
package com.javacodepoint.search;
public class BasicLinearSearch {
public static int linearSearch(int[] array, int key) {
for (int i = 0; i < array.length; i++) {
if (array[i] == key) {
return i; // Key found, return the index
}
}
return -1; // Key not found
}
public static void main(String[] args) {
int[] numbers = { 5, 8, 12, 15, 20 };
int key = 12;
int result = linearSearch(numbers, key);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found.");
}
}
}
2. Linear Search in Java Program (Advanced example)
This program example demonstrates Linear Search on a list of objects, where we search for a specific name in a list of Person objects.
package com.javacodepoint.search;
import java.util.ArrayList;
import java.util.List;
class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "Person{name='" + name + "', age=" + age + "}";
}
}
public class AdvancedLinearSearch {
public static Person linearSearch(List<Person> people, String key) {
for (Person person : people) {
if (person.getName().equalsIgnoreCase(key)) {
return person; // Return the matching Person object
}
}
return null; // Key not found
}
public static void main(String[] args) {
List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 25));
people.add(new Person("Bob", 30));
people.add(new Person("Charlie", 35));
String key = "Bob";
Person result = linearSearch(people, key);
if (result != null) {
System.out.println("Person found: " + result);
} else {
System.out.println("Person not found.");
}
}
}
Key Differences Between the Two Examples
| Aspect | Basic Example | Advanced Example |
|---|---|---|
| Data Type | 1D array of integers | List of objects (Person) |
| Search Target | Integer | String (name property) |
| Result | Index of the key | Object matching the search criteria |
| Flexibility | Limited to primitives or simple data | Works with complex data structures |
Benefits of Advanced Example
- Custom Objects: Works with any class or object, not just primitive types.
- Flexible Search Criteria: Can search by any property of the object.
- Real-World Applications: Suitable for business logic like searching for customers, employees, or products.
Linear Search Efficiency
Time Complexity: O(n).
You can explore other search algorithms like Binary Search, Interpolation Search, Fibonacci Search, Exponential Search, Ternary Search, and Jump Search.