Introduction
In the previous article, we learned the fundamentals of Linear Search, including its algorithm, implementation, time complexity, and basic Java programs.
In this part, we’ll take our understanding a step further by exploring practical applications, advanced implementations, searching in different data structures, recursive Linear Search, and several interview-oriented coding problems.
By the end of this article, you’ll be comfortable applying Linear Search to solve real-world programming problems.
Why Learn Linear Search in Depth?
Although Linear Search is one of the simplest searching algorithms, it appears surprisingly often in software development because many real-world datasets are unsorted.
Examples include:
- Searching a student’s record in a classroom list
- Looking for a customer’s order in recent transactions
- Searching a filename in a directory
- Finding a product in a shopping cart
- Searching logs generated by applications
- Looking for a keyword inside a document
Since these datasets are often not sorted, Binary Search cannot be applied directly, making Linear Search the preferred solution.
Example 1: Linear Search Using User Input
Instead of hardcoding the array, let’s allow the user to enter the values.
import java.util.Scanner;
public class LinearSearchUserInput {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of elements: ");
int n = sc.nextInt();
int[] arr = new int[n];
System.out.println("Enter Array Elements:");
for(int i = 0; i < n; i++)
arr[i] = sc.nextInt();
System.out.print("Enter element to search: ");
int target = sc.nextInt();
int position = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == target) {
position = i;
break;
}
}
if(position != -1)
System.out.println("Element Found at Index " + position);
else
System.out.println("Element Not Found");
}
}
Sample Output
Enter number of elements: 5
Enter Array Elements:
10
25
40
18
60
Enter element to search: 18
Element Found at Index 3
Example 2: Printing All Occurrences
Sometimes an element appears multiple times.
Instead of stopping after the first occurrence, we continue searching.
public class AllOccurrences {
public static void main(String[] args) {
int[] arr = {5,8,5,12,5,20,5};
int target = 5;
System.out.println("Found at Index:");
for(int i=0;i<arr.length;i++) {
if(arr[i]==target)
System.out.println(i);
}
}
}
Output
Found at Index:
0
2
4
6
Example 3: Finding the First Occurrence
public class FirstOccurrence {
public static void main(String[] args) {
int[] arr = {7,2,9,2,8,2};
int target = 2;
for(int i=0;i<arr.length;i++) {
if(arr[i]==target) {
System.out.println("First Occurrence = " + i);
break;
}
}
}
}
Output
First Occurrence = 1
Example 4: Finding the Last Occurrence
Instead of searching from the beginning, search from the end.
public class LastOccurrence {
public static void main(String[] args) {
int[] arr = {7,2,9,2,8,2};
int target = 2;
for(int i=arr.length-1;i>=0;i--) {
if(arr[i]==target) {
System.out.println("Last Occurrence = " + i);
break;
}
}
}
}
Output
Last Occurrence = 5
Example 5: Searching in a Character Array
public class CharacterSearch {
public static void main(String[] args) {
char[] letters = {'A','B','C','D','E'};
char target = 'C';
int index = -1;
for(int i=0;i<letters.length;i++) {
if(letters[i]==target) {
index = i;
break;
}
}
if(index!=-1)
System.out.println("Found at " + index);
else
System.out.println("Not Found");
}
}
Example 6: Searching a Word in an Array of Strings
public class SearchCity {
public static void main(String[] args) {
String[] cities = {
"Delhi",
"Mumbai",
"Pune",
"Lucknow",
"Jaipur"
};
String search = "Lucknow";
boolean found = false;
for(int i=0;i<cities.length;i++) {
if(cities[i].equals(search)) {
System.out.println("City Found at Index " + i);
found = true;
break;
}
}
if(!found)
System.out.println("City Not Found");
}
}
Recursive Linear Search
Linear Search can also be implemented recursively.
Instead of using loops, the function calls itself.
Algorithm
- Compare the current element.
- If found, return the index.
- Otherwise call the function for the next index.
- Stop when the end of the array is reached.
Java Program
public class RecursiveLinearSearch {
static int search(int arr[], int target, int index) {
if(index == arr.length)
return -1;
if(arr[index] == target)
return index;
return search(arr,target,index+1);
}
public static void main(String[] args) {
int arr[] = {12,45,78,34,90};
int result = search(arr,78,0);
if(result!=-1)
System.out.println("Found at " + result);
else
System.out.println("Not Found");
}
}
Output
Found at 2
Searching in a Two-Dimensional Array
Linear Search also works with matrices.
Example matrix:
10 20 30
40 50 60
70 80 90
Search = 80
Java Program
public class Search2D {
public static void main(String[] args) {
int[][] arr = {
{10,20,30},
{40,50,60},
{70,80,90}
};
int target = 80;
boolean found = false;
for(int i=0;i<arr.length;i++) {
for(int j=0;j<arr[i].length;j++) {
if(arr[i][j]==target) {
System.out.println(
"Found at Row "
+ i +
" Column "
+ j);
found = true;
}
}
}
if(!found)
System.out.println("Not Found");
}
}
Output
Found at Row 2 Column 1
Searching Objects
Suppose each student has a name and marks.
class Student {
String name;
int marks;
Student(String n,int m) {
name=n;
marks=m;
}
}
Search by name.
public class ObjectSearch {
public static void main(String[] args) {
Student[] students = {
new Student("Amit",85),
new Student("Rahul",92),
new Student("Priya",88)
};
String search="Rahul";
for(Student s : students) {
if(s.name.equals(search)) {
System.out.println("Marks = " + s.marks);
break;
}
}
}
}
Output
Marks = 92
Searching Using Enhanced for Loop
public class EnhancedLoopSearch {
public static void main(String[] args) {
int[] arr={10,30,45,70};
int target=45;
boolean found=false;
for(int number:arr){
if(number==target){
found=true;
break;
}
}
System.out.println(found);
}
}
Output
true
Searching Using Java Collections
import java.util.ArrayList;
public class ListSearch {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");
if(list.contains("Python"))
System.out.println("Language Found");
}
}
Output
Language Found
Common Applications of Linear Search
Linear Search is frequently used in:
- Contact Management Systems
- Student Record Systems
- Library Management Software
- School Attendance Systems
- Hospital Patient Records
- Shopping Cart Applications
- Banking Transaction Lists
- Employee Management Software
- Inventory Systems
- File Search Utilities
Can Linear Search Be Used on Sorted Arrays?
Yes.
However, Binary Search is much faster on sorted arrays.
For example:
10 20 30 40 50 60
Searching for 60
Linear Search
10
20
30
40
50
60
Total comparisons = 6
Binary Search
40
50
60
Only 3 comparisons.
Optimization for Sorted Arrays
If the array is sorted in ascending order, we can stop early.
Example
10 20 30 40 50 60
Search = 35
After reaching 40, we know that 35 cannot appear later.
So we stop immediately.
for(int i=0;i<arr.length;i++){
if(arr[i]==target){
System.out.println("Found");
break;
}
if(arr[i]>target){
System.out.println("Not Found");
break;
}
}
This optimization reduces unnecessary comparisons on sorted arrays.
Comparison with Other Searching Algorithms
| Algorithm | Works on Unsorted Data | Average Time | Worst Time |
|---|---|---|---|
| Linear Search | Yes | O(n) | O(n) |
| Binary Search | No | O(log n) | O(log n) |
| Hash Table Lookup | Depends | O(1)* | O(n) |
| Jump Search | Sorted Only | O(√n) | O(√n) |
*Average-case performance.
Interview Questions
1. Why is Linear Search called Sequential Search?
Because elements are checked sequentially, one after another.
2. Can Linear Search be recursive?
Yes.
It can be implemented using recursion instead of loops.
3. Does Linear Search require extra memory?
No.
It uses constant extra memory, so its space complexity is O(1).
4. Which is faster: Linear Search or Binary Search?
Binary Search is significantly faster for large sorted datasets. Linear Search is more suitable for unsorted or very small datasets.
5. Can Linear Search find duplicate values?
Yes. If you don’t stop after the first match, it can locate and count all duplicate occurrences.
Practice Exercises
Solve the following without looking at the solutions:
- Search a number entered by the user.
- Print every index where an element appears.
- Count duplicate values in an array.
- Search a character in a string.
- Search a city in an array of city names.
- Search an employee using employee ID.
- Search inside a 2D matrix.
- Write a recursive Linear Search.
- Find the first and last occurrence of an element.
- Search an object in an array of custom objects.
Key Takeaways
- Linear Search examines elements one by one until the target is found.
- It works on both sorted and unsorted data.
- It is simple to implement and requires only constant extra space.
- It can be applied to arrays, strings, collections, matrices, and objects.
- It can be implemented using both loops and recursion.
- For sorted datasets with frequent searches, Binary Search is generally a better choice.
- Mastering Linear Search builds a strong foundation for more advanced searching techniques used in Data Structures and Algorithms.
What’s Next?
Now that you have mastered Linear Search, the next step is to learn Binary Search, a much faster searching algorithm that uses the Divide and Conquer technique. Binary Search reduces the search space by half in every step, making it highly efficient for large sorted datasets and a favorite topic in technical interviews.
