Hey, Folks! Welcome back to my new article which is about Linear Search in Java. In this article, I'll describe all about Linear Search in Java where I'll discuss on various topics. Let's Start by deep-diving into Linear Search.
What is Linear search?
Linear search, also known as sequential search, is a simple searching algorithm used to find a specific element in a list or array. The algorithm works by checking each element of the list sequentially until the desired element is found or the list is exhausted.
Let's see, how can we proceed with the Linear Search?
Procedure
First of all, we should start with the first element of the list.
Then compare the target element with the current element.
If the current element matches the target element, return the index of the current element.
If the current element does not match the target element, move to the next process and repeat the process.
If the end of the list is reached without finding the target, return an indication the element is not present(usually -1 or null).
Example:
Question: Write a function to perform a linear search on an array of integers.
public class LinearSearch {
// Function to perform linear search
public static int linearSearch(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i; // Return the index of the target element
}
}
return -1; // Element not found
}
public static void main(String[] args) {
int[] array = {2, 4, 6, 8, 10};
int target = 6;
int result = linearSearch(array, target);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found in the array");
}
}
}
In this example, the linearSearch function takes an array and a target value as inputs and returns the index of the target if found, or -1 if the target is not in the array. The main method demonstrates how to use this function with a sample array and target value.
How does linear search differ from binary search?
Linear search and binary search are both algorithms used to find a specific element in a list or array. However, they differ significantly in their approaches, requirements, and performance. Here are the main differences:
1. Algorithm Approach:
Linear Search:
Sequentially checks each element in the list from the beginning to the end until the target element is found or the list is exhausted.
Works on both sorted and unsorted lists.
Binary Search:
Divides the list into two halves and repeatedly reduces the search interval by half.
Only works on sorted lists. If the list is not sorted, it must be sorted first before applying binary search.
2. Time Complexity:
Linear Search:
Best Case:
O(1)(target is the first element).Average Case:
O(n).Worst Case:
O(n)(target is the last element or not present).
Binary Search:
Best Case:
O(1)(target is the middle element).Average Case:
O(logn).Worst Case:
O(logn)(requires the logarithmic number of comparisons).
3. Space Complexity:
Linear Search:
O(1)- Requires a constant amount of additional space.Binary Search:
O(1)- For iterative implementation.O(logn)- For recursive implementation due to the call stack.
4. Efficiency:
Linear Search:
Less efficient for large lists as it may require checking every element.
Suitable for small lists or unsorted lists where sorting is not feasible.
Binary Search:
More efficient for large lists due to its logarithmic time complexity.
Requires the list to be sorted, which can add additional time complexity
O(nlogn)if sorting is needed.
5. Use Cases:
Linear Search:
When the list is small.
When the list is unsorted.
When simplicity is preferred over efficiency.
Binary Search:
When the list is large and sorted.
When efficiency is critical.
In what types of data structures can linear search be applied in Java?
Linear Search can be applied to various types of Data Structures in Java, including:
1. Arrays:
You can use linear search to find an element in a one-dimensional or multi-dimensional array.
public static int linearSearch(int[] array, int target) { for (int i = 0; i < array.length; i++) { if (array[i] == target) { return i; } } return -1; // Element not found }2. ArrayList:
- Linear search can be used to search for an element in an
ArrayList.
- Linear search can be used to search for an element in an
public static int linearSearch(ArrayList<Integer> list, int target) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == target) {
return i;
}
}
return -1; // Element not found
}
3. Space Complexity:
- Both singly and doubly linked lists can be traversed using linear search.
public static int linearSearch(LinkedList<Integer> list, int target) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == target) {
return i;
}
}
return -1; // Element not found
}
4. Strings:
You can perform a linear search to find a character in a
String.public static int linearSearch(String str, char target) { for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == target) { return i; } } return -1; // Character not found }5. Custom data structures:
For custom data structures (like custom linked lists or trees), you can implement a linear search based on the structure's traversal methods.
class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } public static boolean linearSearch(Node head, int target) { Node current = head; while (current != null) { if (current.data == target) { return true; } current = current.next; } return false; // Element not found }In general, linear search can be applied to any iterable data structure where elements can be accessed sequentially.
Conclusion
Linear search is a simple searching algorithm that checks every element in a list until it finds the target element or reaches the end of the list. It's straightforward but not very efficient for large lists, as its time complexity is O(n), where n is the number of elements in the list.
The second part of this article will come soon. Thanks, Hope this blog will be helpful to you
Happy Learning!