Searching In programming it is a process of finding a given value position in a list of values. In our daily life it plays such an important role this can be finding something from a collection of data, you may need to find a word from a dictionary or find your friend from the crowd.
Linear/Sequential search
- It is the basic simple search algorithm
- In sequential search, we compare the target value with all the other elements given in the list. for example arr = {18, 12, 19, 77, 29, 50} (unsorted array) target = 77
In the above example, the target value is compared with all the elements in the array in sequential/linear way.
Time Complexity:
Best Case: O(1) -> constant
How many checks will the loop make in the best case i.e the element will be found at the 0th index that is only one comparison will be made for best case.
Worst Case: O(n)
Worst case, here it will go through every element and then it says element not found
public class Main {
public static void main(String[] args) {
int[] nums = {23, 45, 1, 2, 8, 19, -3, 16, -11, 28};
int target = 19;
int ans = linearSearch(nums, target);
System.out.println(ans);
}
// search in the array: return the index if item found
// otherwise if item not found return -1
static int linearSearch(int[] arr, int target) {
if (arr.length == 0) {
return -1;
}
// run a for loop
for (int index = 0; index < arr.length; index++) {
// check for element at every index if it is = target
int element = arr[index];
if (element == target) {
return index;
}
}
// this line will execute if none of the return statements above have executed
// hence the target not found
return -1;
}
}
Solved my first leetcode question with linear search check it out Even number of digits
For further explanation about linear search algorithm, kindly check out this wonderful toturial Linear Search in Java by Kunal Kushwaha
Feel free to connect with me on github and Linkedin, thank you.