Linear Search

Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set.

How Does Linear Search Algorithm Work?

• Every element is considered as a potential match for the key and checked for the same.
• If any element is found equal to the key, the search is successful and the index of that element is returned.
• If no element is found equal to the key, the search yields “No match found”.

Time Complexity

Binary Search

Binary Search is defined as a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N).

Conditions for Binary Search :

• The data structure must be sorted.
• Access to any element of the data structure takes constant time.

Time Complexity

Binary Search Algorithm:

• Divide the search space into two halves by finding the middle index “mid”.
• Compare the middle element of the search space with the key.
• If the key is found at middle element, the process is terminated.
• If the key is not found at middle element, choose which half will be used as the next search space.
  • If the key is smaller than the middle element, then the left side is used for next search.
  • If the key is larger than the middle element, then the right side is used for next search.
• This process is continued until the key is found or the total search space is exhausted.

Ternary Search

Ternary search is a search algorithm that is used to find the position of a target value within a sorted array. It operates on the principle of dividing the array into three parts instead of two, as in binary search.

• partitionSize = (right - left) / 3
• mid1 = left + partitionSize
• mid2 = right - partitionSize

Conditions

• target > mid2
• target == mid2
• target < mid2 && target > midl target == mid1
• target < mid1

Time Complexity: $Log_3(n)$

<aside> 🎯 Binary search is faster than ternary search

</aside>

Jump Search

Like Binary Search, Jump Search is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

blockSize = sqrt(n)

How Does Jump Search Algorithm Work?

ARRAY = (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610).

Find 55 with the following steps assuming that the block size to be jumped is 4.

• Jump from index 0 to index 4;
• Jump from index 4 to index 8;
• Jump from index 8 to index 12;
• Since the element at index 12 is greater than 55, we will jump back a step to come to index 8.
• Perform a linear search from index 8 to get the element 55.

The increasing order of performance is:

linear search < jump search < binary search

<aside>

Time Complexity: $O(\sqrt n)$

</aside>

Exponential Search

The name of this searching algorithm may be misleading as it works in O(Log n) time. The name comes from the way it searches an element.