Algorithms 101: Searching

#computers

Searching algorithms play a vital part in many programs. It is also a common and well-studied task. So, I figured I’ll write a post for myself to understand more on them. Mostly in the questions online we may find that task as:“Given a list of values, and the desired value. Find the position of the desired value in the list.”So, when we encounter such questions we need a searching technique to search the given list or array of values and find the required value. There are numerous searching techniques but mosly they rely on the construction of more complex data structures and do the repeated searching via the below most famous techniques.

This is the most basic kind of search method. As the name suggests it involves going through an array or a list in a linear manner i.e, checking each element until the required element is found. It has a time complexity of O(n), which means the time is linearly dependent on the number of elements, which is not so bad but it shits the bed if the list or array is large af. Thus, it’s better to use the linear search for an unsorted and unordered small list of elements.

for(start to end of array)
{
if(current element equals to the required element)
{
print(current element index);
}
}

Let there's an array with elements {26,4,5,72,8,1} and the required value is 8. So, the code will be as follows:

This is a better way to search an array in terms of time complexity. Binary search looks for a particular item by comparing the middlemost item of the array or list. If the middle element is equal to the required one then we write that. If it is not equal then we check if the middle term is greater than the required item and if yes, then the required item is searched in the sub-array to the left of the middle item. Otherwise, we search for the item in the sub-array to the right of the middle item. This algorithm has a time complexity of O(logN) which is a very good time complexity when we're searching for a list or array of a big size. But the only issue with this is it works only when the array or list is pre-sorted else it won't even work.

let mid, lowerbound=0, upperbound=array.length-1;
while(lowerbound ≤ upperbound)
{ 
mid will be equal to lowerbound+(upperbound-lowerbound)/2;
if(if mid is equal to required element)
{
return index of mid
}
if(if mid is greater than required element)
{
make lowerbound as mid+1;
}
else
{
make upperbound as mid-1};
}
}
return -1 if the element isn't there

Let there's an array with elements {22,23,24,25,26,27} and the required value is 23. So, the code will be as follows:

So, this sums up the two major searching algorithms. As, I've said earlier there are many but they involve more majore ds and repeated searching based on these.