Searching Algorithms as the names indicates are used to searching records or information from a give data set. here today i would love to talk about the two of such algorithms which are Linear & Binary Search Algorithms.
Linear Search Algorithms
A Linear search algorithm is nothing special but a loop to find a particular item from a collection of data. here an item is given to be found in mostly an unsorted order. When the Collection or the array is unsorted the first approach that comes to mind for solving these problems is a linear sort. Let’s take a look at such examples.
Given a set of data in an array, [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] Find the position of 5 in the collection or if not found return -1.
to this simple problem i know what you’re thinking, the answer is 4 🙂 just kidding…
Well it’s obvious the position of 5 in the array is 4 anyway and am sure it’s because the collection is made up few elements and it’s very easy to identify. imagine you have the same collection but this time around with millions of records to find a given number, that’s why my friend we need a computer to do this boring work not only finding that but with with preciseness and speed. it will definitely take some time to execute but will be far far better that human computation in this case. let’s take a look at a simple solution to this simple problem.
function linearSearch(arr, val) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === val) return i;
}
return -1;
}
let data = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
let n = 10;
linearSearch(data, n);
with the solution the input returns definite -1 by running which means the requested information is not found in the give collection, try search for 5 as mentioned in our main problem. there you have it your predicted position number 4 comes up as your answer. you can play around with the code to try and understand how it’s written and how best you can refactor to get a better result. find out the best and Worst Case scenario (Big O Notation of the solution).
Linear Search could get much more complicated when dealing with much complex concepts, for instance given a string you are required to find a pattern that matches part of the string provided. let’s take a look.
function patternSearch(long, short) {
let count = 0;
for (let i = 0; i < long.length; i++) {
for (let j = 0; j < short.length; j++) {
if (short[j] !== long[i + j]) break;
if (j === short.length - 1) count++;
}
}
return count;
}
patternSearch('cats are lovely', 'love');
with the same concept here we’re looping or iterating through the string starting from the main string denoted by long then jumping onto the short pattern to match the long with and here you will notice each character of the short need to compared with at least two of the combined characters in the long string, if a character from i & j matches then try and match j & j+1 with i + j i know it can be pretty much confusing, but you could take your time to better anylise the solution above to grab the concept. Once that is done you’re free to Go :), don’t mind me you can go anytime you like. Oh i forgot to mention that this solution is of O(n²) Big O Notation.
Binary Search
Binary search in the other hand can only be performed on an already sorted collection of data. if the collection is not sorted and you’re not required to use specifically a binary search ? you can opt to use Linear search, which is one of the most basic searches embedder some inbuilt JavaScript methods ie. data.map(), data.filter(), data.find() etc…
so you’re not forbidden in this case, but if the requirement insist you use Binary search and the collection in unsorted then you need to sort the collection in a regular order before executing your Binary Search Algorithms. Okay what makes this Algorithm unique from linear search.
Binary search has two ways of being solve: through the iterative method or using recursion. remember our last section i said recursions are just the alternatives to for loop ?. ooh Yes this is the case. Now with binary search we use the Divide and Conquer approach which requires you to have a low/start/left & high/end/right with an average which is called the median of the size of your collection. you can use either term in solving a divide and conquer approach, we will see that in a sec. so after gathering your three elements it’s time to do some comparism, first you check if the the value you’re to look for is not equal to the median and the low (mostly the starting point) is never greater than the high (the end point) if so then the item you’re looking for does not exist in the collection. if the condition is true then compare if the value is greater or less to the median if greater then shift your low in front of the median (median +1) position and rebegin your compearism. If the value is lesser than the median value then bring your high before the median value (median – 1) position and continue with the comparism. with doing this you can clearly see you’re narrowing down your search strategy and eventually if those conditions can not be met anymore it means only two things your middle value or median is equal to your value or it does not exit which in turn returns 0 or -1. let’s now take a look at the iterative way of representing the above explanation.
function binarySearch(arr, value) {
let low = 0;
let high = arr.length - 1;
let middle = Math.floor((low + high) / 2);
while (arr[middle] !== value && low <= high) {
if (value < arr[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
middle = Math.floor((low + high) / 2);
}
if (arr[middle] === value) {
return middle;
}
return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5], 2));
Time Complexity O(log n)
i hope that helps you to more understand the concept. thinking of it that way is much more easier to flow with i guess. Kindly use the same concept and solve this with the recursive method to see which you will be much comfortable with. binary search can also be implemented on trees which we will have a look at soon.
Take care of yourself until next time.!