linear Search - is algorithm which starts searching from index 0 till the element finds.
This algorithm also worst-case algorithm. If element not available, it iterates through the elements till end.
Best Case - O(1)
Worst case - O(n) where n is the size of the array.
public class LinearSearch {
public static void main(String[] args) {
int[] arr = new int[5];
for(int i=0;i<arr.length;i++) {
arr[i]=i;
}
int target = 2;
System.out.println("element found in the array at index " +linearSearch(arr, target));
int targetNotInArray = 100; // to prove worst case
System.out.println("This will iterate through the array and element "
+ "is not found in array and return false" +
linearSearch(arr, targetNotInArray));
}
static int linearSearch(int[] arr, int target) {
if (arr.length == 0) { // if the array has no element
return -1;
}
// looping through the array to find element
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
}
Top comments (3)
Two very minor errors in your post.
First, you indicate worst case is o(n). It is actually O(n). Casing matters. Your o(n) means strictly lower order than n (i.e., it excludes same order as n). While O(n) means at most order n. Little o and Big O relate to each other in a similar way as < and <= relate to each other.
Second, best case should be O(1) and not o(1) for the same reason.
Made the corrections. Thanks for letting me know the errors. I am a learner learning as well as making post here it helps me a lot.
You're welcome