Searching algorithms : learn different searching techniques .

Introduction :

When you write some code or try to build any kind of application you will for sure work with many different data types , one of the problems that you will face is searching for a one value in a bunch of values that you have in any kind of data that you are dealing with as an example we can say that we are working with a list of numbers and at some point we need to check if a cretin value exist or not here we user what we call searching algorithms .

Searching algorithm varies from one to another in terms of how they will find the data that you are searching for , time complexity to find that value and how you can apply or use theme in your situation.

One of the most important factor is to use the best algorithms for your situation so you will be sure that you code will take the minimum searching time and to do that you need to know at least the most famous searching algorithms and there different searching mechanics, once you do that you will have a general idea on how they work and you can even tweak there implementation to create what best suits you in your problem .

In this article we will talk about some famous searching algorithms how they work and there time complexity we will start with the basic one linear searching then we go to more advanced and less time complexity ones like binary search.

Different searching algorithms apply to different data structures so some searching logarithms apply to all data structures and some to only a specific data structure or after applying some condition to that data structure like sorting the data.

Usually searching is talked over with sorting algorithms but this article focus only on searching and the next one will focus on sorting algorithms so we can talk a little bit in detail for each one.

Searching algorithms types :

Sequential search :

a sequential search method is when you go through all the items trying to find the value that you are searching for,when you find it the searching stops in case the value does not exist you will have to loop over all the items then you quit when you reach the end, as an example the linear searching.

Interval search :

In the intervals searching we do not iterate through all the items instead of that and based on some condition or a technique that the searching method use we minimize the searching area and by that we minimize the searching time . as an example if you are searching in an ordered data structured you can split the DS based on the value that you are searching for and search in one half only as an example the binary search.

Linear searching :

This is the most simple and easy type of searching basically you go through all the items and check one by one if the current value equals the value that you are searching for in case the value does not exist you will go through all the data structure value , the time complexity will be O(n) in worst time where n is the size of the data structure.

The linear search has tow variants an ordered linear search and a non ordered linear search.

The ordered linear search is the normal case and do as we said in the previous paragraph but in the ordered linear search we add one condition that is if the value does not equal to what we are searching and if it’s greater we immediately return value not found and stop the searching process cause logically if it’s ordered then your value does not exist, we need to add a new instruction that is the comparison but sometimes it will save you some time the complexity will still at worst O(n).

Jump searching :

The idea of the jump search is that we have a “j(index)” number that indicates the number of jumped blocks then we jump each time j blocks so it will be like first time = j jumps, second time= 2j jumps, 3j…etc , until we find an interval where the searched value may be there and we perform a linear search in that interval to minimize the search area.

The time complexity of this method will be O(√n).

Chunk searching :

In this method what we do is split the ordered DS into chunks (x chunks) and for each chunk we compare the last element of the chunk with our value and based on that we decide which chunk we search in and chunk it again until we find the value or reach a state where we can no more chunk the data so the value does not exist.

The complexity will depend on the number of chunks and the size of each chunk bu it will be better than a linear search in most cases.

Binary Searching :

In binary search what we do is somehow similar to the chunk search but this time we have a pattern and a more organized way of how we will divide the data structure that we area searching in .

The technique is that after we have an ordered data structure we divide the data structure in 2 parts and after we compare the last element of the first part and the first element of the second part with our value we decide where are we going to search an pick only one portion then we repeat the process each time divide by 2 the decide which part to take based on the comparison with searched value. At one point we reach blocs that has only one element where we compare that element with the value that we are searching for and return true or false.

This data dividing each time will lower the time complexity from O(n) to O(log2 n) if you want to know more about how this happened you can read this article about complexity : https://gourineayoub-prf.medium.com/data-structure-and-complexity-a-programmer-best-tow-weapons-part-1-introduction-a941cda2f557

another trick is that you can divide by 4 8 …etc and the log base will change based on that so if you divide by 4 the complexity will b O(log4 n).

Interpolation search :

The interpolation search is better version of the binary search where the binary search will always split the data in half the interpolation search not do instead of doing that it will decide where to split based on the searched value.

This method will search for a position wehre to search and this position is calculated with a formula that is :

pos = startIndex + [ (x-array[startIndex])*(endIndex-startIndex) / (array[endIndex]-array[startIndex]) ].

in this image e = the value that we are searching for and A is the data structure.

this formula was derived from the general line equation y = m*x +c cause the values are linearly distributed in an sorted array.

So each time we calculate the pos if it the same as the value than we return true if not we calculate the pos for the left and right array from that pos and we repeat that until we find our value or array is empty.

Additional resources :

For more comparison about the searching methods you can read this short article : https://www.researchgate.net/publication/314175061_A_Brief_Study_and_Analysis_of_Different_Searching_Algorithms

Conclusion :

• searching methods are a must know techniques that you will need in your programming journey and knowing how each technique work will make your program more efficient has less time complexity.
• as long as you understand this technique you can tweak them if it suits your problem better.
• to search for a value you have to first understand the type of that value I mean the data structure an how does it work that you should think about how to search about it cause some object or customized data structure may have some data or elation between them that can be applied to create some formula to find the element in a much faster way.