Linear Search in Java
Linear Search in Java
Before learning Linear Search In Java, first we have to clear our concepts of Linear Search. i.e. Linear Search is a basic and straightforward search technique where each element in a list or array is checked one by one in sequence.
In this method, we start from the first element and move forward, comparing each item with the target value:
- This process continues until the target value is found or we reach the end of the list.
- Since each element must be checked individually, Linear Search may require up to n comparisons in the worst case, where n is the number of elements.
It’s ideal for small datasets or when data is stored in structures like linked lists.
What is Linear Search?
Linear Search, also known as Sequential Search, is the simplest searching algorithm.
- It checks every element in a list or array sequentially until it finds the target element or reaches the end of the list.
- It is mainly used when the list is unsorted or small.
How Linear Search Works ?
- Start from the first element of the array.
- Compare the current element with the target element.
- If it matches, return the index of the element.
- If it doesn’t match, move to the next element.
- Repeat until the element is found or the entire array is traversed.
- If the element is not found, return -1 (indicating the element does not exist in the array).
1. Iterative Linear Search
Iterative Linear Search is the most common form of linear search where a loop (like for or while) is used to go through each element in the list or array one by one.
How it works:
- Start from the first element.
- Compare each item with the target value.
- Stop and return the position if found, or return -1 if the value doesn’t exist in the list.
Code Snippet:
public class LinearSearch {
// Iterative linear search method
public static int linearSearchIterative(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // element found, return index
}
}
return -1; // element not found
}
}
2. Recursive Linear Search
Recursive Linear Search uses recursion (a function calling itself) instead of a loop to search through the elements one by one.
How it works:
Check the element at the current index.
If it matches the key, return the index.
If not, call the function again with the next index.
Stop when the end of the list is reached or the element is found.
Code Snippet:
public class LinearSearch {
// Recursive linear search method
public static int linearSearchRecursive(int[] arr, int target, int index) {
if (index >= arr.length) {
return -1; // base case: element not found
}
if (arr[index] == target) {
return index; // element found
}
return linearSearchRecursive(arr, target, index + 1);
}
}
Algorithm for Interative and Recursive Linear Search
1. Iterative Linear Search Algorithm
LinearSearch(arr, key)
1. Start from index i = 0
2. Repeat until i < length of arr:
a. If arr[i] == key:
Return i (element found at index i)
b. Increment i by 1
3. If loop ends without finding the key:
Return -1 (element not found)
2. Recursive Linear Search Algorithm
RecursiveSearch(arr, key, index)
1. If index >= length of arr:
Return -1 (reached end, not found)
2. If arr[index] == key:
Return index (element found)
3. Else:
Return RecursiveSearch(arr, key, index + 1)
Learn DSA
Prime Course Trailer
Related Banner
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Complete Java Program Demonstrating Linear Search
Space and Time Complexity:
Space Complexity: O(n) (due to recursion stack)
Space Complexity: O(1)
- Time Complexity: In the worst case, linear search traverses the entire array, hence O(n).
- Space Complexity: Iterative approach uses constant extra space, but recursive approach uses O(n) space due to function call stack.
public class LinearSearch {
// Iterative method
public static int linearSearchIterative(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return -1; } // Recursive method public static int linearSearchRecursive(int[] arr, int target, int index) { if (index >= arr.length) {
return -1;
}
if (arr[index] == target) {
return index;
}
return linearSearchRecursive(arr, target, index + 1);
}
public static void main(String[] args) {
int[] numbers = {5, 3, 8, 6, 2, 10};
int target = 6;
int iterativeResult = linearSearchIterative(numbers, target);
int recursiveResult = linearSearchRecursive(numbers, target, 0);
if (iterativeResult != -1) {
System.out.println("Iterative: Element found at index " + iterativeResult);
} else {
System.out.println("Iterative: Element not found");
}
if (recursiveResult != -1) {
System.out.println("Recursive: Element found at index " + recursiveResult);
} else {
System.out.println("Recursive: Element not found");
}
}
}
Sample Input:
int[] numbers = {5, 3, 8, 6, 2, 10};
int target = 6;
Output:
Iterative: Element found at index 3 Recursive: Element found at index 3
Edge Cases and Handling
- Empty array: If the array length is 0, the function returns -1 immediately.
- Target not found: Returns -1 indicating absence of target.
- Multiple occurrences: Returns the first index where the target is found.
- Array with one element: Checks and returns index 0 if it matches or -1 if not.
Conclusion
Linear search is a fundamental searching algorithm ideal for small or unsorted datasets. It is easy to implement, understand, and serves as a foundation before learning more efficient search techniques such as binary search.
Both iterative and recursive methods have their place depending on the use case, with iterative being more space efficient.
FAQ's related to Linear Search in Java
Answer:
Linear search is best suited for:
- Unsorted arrays or lists where binary search cannot be applied.
- Small datasets where performance differences are negligible.
- Situations where only a single pass through the data is required (e.g., finding the first matching value).
Answer:
Linear search has the following limitations:
- Inefficient for large datasets due to its O(n) time complexity.
- It does not leverage any sorting order of data.
- Repeated searches can lead to performance bottlenecks in big applications.
Answer:
Yes, linear search can be adapted for:
- Strings using equals() for comparison instead of ==.
- Objects, provided you override the equals() method correctly and compare based on relevant fields.
Answer:
Recursive linear search is functionally equivalent but uses more memory due to recursive calls.
Iterative approach is more space-efficient and preferred in practice, especially for larger datasets.
Answer:
Linear search returns the index of the first occurrence of the element. If you need all occurrences, you must continue searching the entire array even after the first match.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment
explain how to calculate space complexity
time complexity is calculated by the number of lines that will be executed at run-time depending on the number of inputs.
space complexity is calculated by the number of more variables required to execute the program.
here the line written in the for loop will be executed n(number of inputs) times, so time-complexity is O(n).
and we require two(a constant number of) variables during the execution of the whole program, so space-complexity is O(1).