Linear Search is probably the easiest searching technique that is available in computer programming. You simply need to iterate over each element in a list sequentially and compare if it matches the element to search.
Searching is a prime concept, as it gives you a starting point to your code. Even in real life, if you plan to go to a movie, a vacation or a shopping mall, the first thing you do is search for a location. Similarly, in programming you could have a search for anything. Google has become a search giant by just leveraging this simple requirement.
Writing a search algorithm as big as Google would be very tricky, but hey…we need a starting point. Linear search is the best way to dive into it.
Example:
Let us say you are given with this example array:
You are given with 2 numbers to search: 7 and 25. A linear search algorithm would look something like:
- Start from the first element.
- Check if it matches the target element.
- If yes, we found the element.
- Else, move ahead and check again.
- Repeat the above process till you reach the end of the array.
In our example, we can find 7 in the array but not 25.
public static boolean linearSearch(int[] arr, int numberToSearch) {
boolean found = false;
// Search sequentially through each element
for (int i = 0; i < arr.length; i++) {
if (arr[i] == numberToSearch) {
found = true;
break;
}
}
return found;
}
Code language: Java (java)This technique to search is however really slow and we may have to traverse the entire array before we can come to a conclusion. If the array is sorted, we can get some improvements.
Sorted Linear Search:
Let us say once again we have our sample array, but this time we sort it.
The bottom array is now sorted. We can derive an advantage from it. Let us say we are trying to search for the number 6 in this array. As per the linear search algorithm, you start from the beginning at 0. As soon as you start moving ahead you keep comparing numbers to 6.
Once you reach the element 7, you realize that 7 > 6. Hence, we can stop now and we don’t need to look further. That is because the array is sorted. It implies that all further elements would be definitely greater than 7 and hence we can save some computation time.
Implementation:
public static boolean sortedLinearSearch(int[] arr, int numberToSearch) {
boolean found = false;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == numberToSearch)
found = true;
// If arr[i] is greater than the numberToSearch, we can simply exit
// as we would not be able to find the number further
if (arr[i] > numberToSearch)
break;
}
return found;
}
Code language: Java (java)Time Complexity: O(n)
Space Complexity: O(1)
The code and the test cases can also be found on GitHub.
Note: We can make the above algorithm even faster by making further improvements by incrementing the index at a faster rate. This will reduce the number of comparisons for searching in the sorted list.
Video Explanation:
