Algorithms (Search)

WE BEGIN
Before you begin this article do make sure you have read the article on BigO notation cause this takes some things from there, this article assumes you have read the BigO Notation article.
This Algorithm series will be in two parts one talking on search algorithms and the other talking on sorting algorithms. Today we are going to talk about searching algorithms. 
When we talk about the search algorithm we can think about Google search where you type in something and it takes you to your result depending on your search. This is of course way too complicated for the scope of this article but technically that is what searching is. Searching can also be seen in a music player where a user types the name of the song he/she wants to listen to and the song is brought out by the app.
WHAT IS AN ALGORITHM
In simple terms, this is a process or set of steps to accomplish a certain task. A lot of algorithms exist out there.  Computer Scientists have been creating algorithms for a long long time. Some algorithms are faster than some in certain situations and some are slower than some in certain situations. The key is to know which algorithm to use or which algorithm is better situated to use in a particular situation.
WHERE DOES ALGORITHM COME UP IN SEARCHING
Considering a huge data set again just like we did in the BigO Notation if a user is trying to search through a billion elements in an array to find a particular one thing the algorithm that the program uses to search becomes important. We need to find the most efficient way to find the element so as we don’t cause lag in the application.  In this article, we will look at two searching algorithms 

• Linear Search Algorithm
• Binary Search Algorithm

LINEAR SEARCH ALGORITHM
Given an array, the simplest way to search for value is to look at every element in the array and check if it’s the value that we want. Javascript has search built into it in the form of different methods which are

• indexOf
• Includes
• Find
• find Index

BUT HOW DO THESE FUNCTIONS WORK
Being that we are under that Linear search of course these methods uses the linear search algorithm.
LET US LOOK AT HOW LINEAR SEARCH WORKS
[ 5,  7, 2,  8, 9, 10 ]
Using the above array, let us look for 9 our Linear algorithm will start from the first item which is 5 and ask itself, is 5 equal to 9, of course 5 is not equal to 9 so it goes to the next element in the array and asks again, is 7 equal to 9, it is not so it goes to the next element, it does this till it gets to 9, when it reaches 9 it asks itself is 9 equal to 9 of course it is so it brings out 9 for you. 
LINEAR SEARCH PSEUDOCODE
The step by step process of how we will write the Linear search is a follows

• A function accepts an array and a value
• Loop through the array and check if the current array element is equal to the value
• If it is, return the index at which the element is found
• If the value is never found, return “value not found”
• 

LINEAR SEARCH BIGO
We will use three cases to define the BigO of Linear Search,

• The Best case
• The Average case 
• The Worst case

The best case of Linear search is O(1), meaning constant time. This is an excellent time complex in regards to BigO, but this is rarely the case in most situations. This case occurs when the item or element that is being searched for is the first element in the array. Let me explain more, looking back at the array that we created already let’s say we are looking for 5 which is the first element in the array, our algorithm looks at the first element and asks if 5 is equal to 5? Yes5 is equal to 5 and therefore it returns the index.
The average and worst case of Linear Search is O(n), meaning linear time. This case occurs when the item or element that is being searched for is not the first element in the array. So once our algorithm looks at the first element and it does not match it moves to the next till it eventually finds the match, it may find it at the middle of the array or at the end of the array. It keeps iterating till the end of the array.
BINARY SEARCH ALGORITHM
Binary Search is a much faster form of search, rather than eliminating one element at a time it can eliminate half of the remaining elements at a time(will explain). Binary search only works on sorted arrays. 
Binary Search uses the DIVIDE AND CONQUER 
LET US LOOK AT HOW THE ARRAY WORKS
[ 1,   2, 4,   8, 9, 11,   13, 17, 20,   21, 27, 23, 77 ]
Let us look for 17 using the Binary Search algorithm. We start by picking the middle element of the array by dividing the length of the array by 2 and rounding down if the result is in decimal form. Then we find the element in the index of the result. From that index we check if that element we are looking for is less than the result. Let’s say 13 is the middle element, we check if 17 is less than 13 since 17 is not less than 13 we remove all the elements before 13 because our answer is definitely not in that part of the array. What are we left with 
[ 13,   17, 20,   21, 27, 23,   77 ]
We repeat this again with this array. We pick the middle let us say 21 and ask if 17 is less than 21? Well 17 is less than 21 nor is it equal to 17 so it is definitely not greater we remove all the element after 21, What are we left with
[ 13,   17, 20,   21 ]
Taking our middle element as 17 it asks is 17 less than 17, is it greater than 17 or is it equal to 17. 17 is equal to 17 so it returns our index 
BINARY SEARCH PSEUDOCODE
The step by step process of how we will write the Binary search is a follows

• This function accepts a sorted array and a value
• Create a left pointer at the start of the array, and a right pointer at the end of the array
• While the left pointer comes before the right pointer:
  • Create a pointer in the middle
  • If the value is found return the index
  • If the value is too small, move the left pointer up 
  • If the value is too large, move the right pointer down
•  If you never find the value, return ‘value not found’

BINARY SEARCH BIGO
We will use three cases to define the BigO of Binary Search,

• The best Case
• The Average Case 
• The worst Case

The best case O(1) constant time is also the same explanation as the linear best case. The first element can be what we are looking for so it returns the index immediately.
The Average and Worst case is O(log n). 
[2,4,5,9,11,14,15,19,21,25,28,30,50,52,60,63]
Breaking this down using our algorithm it takes 4 steps to do this. This array has 16 elements and it takes 4 steps log2 = 16. Anytime we double the number of elements we are only adding one extra step.
 
 
 

Written by Ebube Okocha.