Search Algorithms

Today, let us touch base on some fundamental concepts like search algorithms.

In simple terms, searching is a process of looking up a particular data record in the database or in the collection of items. A search typically answers as true or false whether the particular data in which we are referring is found or not and perform the next action accordingly.

Commonly used algorithms for search are:

• Linear search
• Binary search
• Interpolation search

Let us understand them in detail with some example

Linear Search Algorithm

Linear Search Algorithm is the simplest and easiest form of the search algorithm. In this algorithm, a sequential search is made over all the items one by one to search for the targeted item. Each item is checked in sequence until the match is found.

If the match is found, the searched item is returned otherwise the search continues till the end.

To make it easy to understand, let us see understand linear search using a flow diagram and example.

Points to note:

1. Does not need sorted array list
2. Performs equality comparisons
3. The time complexity is O(n)
4. Time taken to search elements keeps increasing as the number of elements is increased.

Binary Search Algorithm

In Binary search algorithm, it begins with an interval covering the whole array and diving it in half.

If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

To make it easy to understand, let us see understand binary search using flow diagram and example as below.

Points to note:

1. The array needs to be sorted
2. Performs ordering comparisons
3. Time complexity to O(log n).
4. Search is done to either half of the given list, thus cut down your search to half time

Interpolation search Algorithm

Interpolation search is an improved version of binary search. This search algorithm works on the probing position of the required value. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, the interpolation search is likely to start search toward the end side. To find the position to be searched, it uses the following formula.

position = lowVal + [ (s-array[lowVal])*(highVal-lowVal) / (array[highVal]-array[lowVal]) ]

array[] => Array where elements need to be searched
s => Element to be searched
lowVal => Starting index in arr[]
highVal => Ending index in arr[]

Algorithm is same as binary search except that here we determine the probe position based on the above formula

Points to note:

1. The array needs to be sorted
2. Improved version of Binary search algorithm
3. Time complexity to log(log(n))

Hope this article helps refresh your basic concepts. I will come up with more articles to revise and touch base on legendary and foundational concepts.