Search algorithms and their implementations
As the name suggests, searching algorithms find and retrieve a data item within a data structure. One of the popular use-cases of search algorithms is a search engine. Search engines like Google, AOL, Bing, and Yahoo utilize search algorithms to quickly crawl and index billions of information on the internet to get a user a piece of the requested information. The algorithm’s efficiency determines how fast the search engines can retrieve this information and the abundance of information in their index.
In real life, there are diverse ways we search for items. The way librarians search for books differs from searching for keys in their bag, a word in a dictionary, or a product on a supermarket shelf.
For a computer program, it is no different. Several search algorithms cater to various search processes. They include:
- Linear search
- Binary search
- Jump search
- Sublist search
- Interpolation search
- Fibonacci search
Linear Search
A linear search starts its search at the beginning of the data structure or list, works its way sequentially through each data element until it reaches the item it is searching for at the end of the list.
It is a simple algorithm but highly inefficient. A list containing a few elements works well with this algorithm, but it becomes inept when we have a considerable number of pieces. Say we have a million features in the list, and the item we need is at the 900,000th index. In such a case, a linear search will go through over 800,000+ items to get to its intended element. That is a lot of time spent processing.
The time complexity for a linear search is 0(n). It means execution time increases as the number of elements increases. We use this algorithm with unsorted and sorted elements.
The Algorithm
STEP 1:
Start searching at first element (i)
STEP 2:
Move to the second element and repeat for all elements
STEP 3:
At current element, check if it is the required element
IF TRUE
PRINT 'Element found at index number'
STEP 4:
Until FOUND == TRUE, or element not found, Repeat search till th
STEP 5:
STEP 6:
Code implementation in Javascript
nums = [1, 2, 23, 4, 11, 77, 55, 44, 33, 67]
a = 4
function LinearSearch(nums, a)
{
let results = []
for (let i = 0; i < nums.length; i++)
{
if (nums[i] === a)
{
results.push(i)
}
}
// return -1 when the results array is empty
if (!results)
{
return -1
}
// else return results
return results
}
document.write(LinearSearch(nums, a))Code implementation in Python
index = -1
nums = [10, 18, 9, 4, 66, 90, 2, 16, 34, 65]
a = 34
def linear_search(nums, a):
i = 0
while i < len(nums):
if nums[i] == a:
globals()['index'] = i
return True
i = i + 1
if linear_search(nums, a):
print('Number found at index', index + 1)# specify the index the number is found at
else :
print('Number not found')
print(linear_search(nums, a))Binary Search
Unlike linear search, binary search picks a midpoint in the data structure and divides the elements into two, from that point. It works only with sorted elements since it must determine if the item it is searching for is higher or lower than the other two sides. It chooses the next midpoint of the search based on this.
If the element it searches for is more significant than the midpoint, it moves to the right side with higher values and searches there. If the searched item is lower, it moves to the left side. If the element is equal to the midpoint, it stops its search there. We continue with this process until we get what we want.
Binary search is considered a more efficient algorithm than linear search. It divides elements and quickly discards elements not worth its time and moves to more relevant details. The time complexity is 0(log n).
A drawback with Binary Search is that if multiple occurrences of a particular element exist in an array, it does not return the index of that first element but the index closest to it.
An array containing the following values [1,2,3,4,4,5] returns a 3 if we search for 4.
The Algorithm
STEP 1:
Start
STEP 2:
Determine the middle item in the list using the formula;
mid = low + (high - low) / 2
to set a midpoint.
STEP 3:
Compare the value of the middle element to the element being searched for.
STEP 4:
IF TRUE, GOTO STEP 7
ELSE
STEP 5:
IF target element is > middle element,
THEN
discard the left hand side of the list
ELSE
STEP 6:
IF target element is < middle element
THEN
Discard the right hand side of the list
ENDIF
STEP 7:
Repeat process 2-6 and iteration until target element == Trueor no more item
STEP 8:
Start
Code implementation in JavaScript
//program to write binary search algorithm
function binary_search(num, index)
{ //num is the array, index the target element
let start = 0;
let end = num.length - 1;
while (start <= end)
{
let midpoint = Math.floor((start + end) / 2);
if (num[midpoint] === index)
{
// Found the element
return midpoint;
}
else if (num[midpoint] < index)
{
// if the index is less than the midpoint, the program keeps searching to the right
start = midpoint + 1;
}
else
{
// if the index is greater than the midpoint, the program continues searching to the left
end = midpoint - 1;
}
}
// index not found
return -1;
}
let num = [1, 2, 3, 4, 5, 6, 7, 8, 9]
let index = 7
document.write(binary_search(num, index))Code Implementation in Python
sequence_a = [2, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14]
index = 6
def binary_search(arr, item):
beg_index = 0
end_index = len(arr) - 1
while beg_index <= end_index:
midpoint = beg_index + (end_index - beg_index) // 2
midpoint_value = arr[midpoint]
if midpoint_value == item:
return midpoint
elif item < midpoint_value:
end_index = midpoint - 1
else :
beg_index = midpoint + 1
return None
if binary_search(sequence_a, index):
print('Number', index, 'found')
else :
print('Number not found')
print('At index', binary_search(sequence_a, index))Fibonacci algorithm
Are you familiar with the mathematical Fibonacci sequence? The Fibonacci algorithm is the same as the Fibonacci sequence and follows the same logic. In programming, the Fibonacci sequence provides an intricate side-view when it comes to determining the difference between loops and recursion.
Fibonacci sequence is a group of numbers, starting from 0 where the next number is an addition of the last number + the current number. So we have:
0, 1, 1, 2, 3, 5, 13, 21, 34...
Usually, the first number is initialized to either a 0 or 1, depending on where we want to start counting. Fibonacci algorithms work with three numbers, the first number, the following number after it, and their sum. If we initialize to 0, the following number is 1, and the value of the next number is 0+1, which is 1, after which we add 1 + 1 to give us the following number 2.
0,1,1,2...
Calculating for a Fibonacci sequence is calculating the nth term of a set of sequences. The nth term is the sum of the (n-1)th and the (n-2)th term. The formula for this is,
tn = tn-1 + tn-2
The time complexity for the Fibonacci algorithm is 0(log n), just like a binary search. One of its uses is in the financial trade market, where Fibonacci numbers serve as technical indicators.
Algorithm
STEP 1:
Start
STEP 2:
Declare the variables for the first, second, third numbers, increment and nth position (x, y, z, i, n)
STEP 3:
Initialize the variables, x = 0, y = 1 and c = 2
STEP 4:
Get the value of the number of terms, n
STEP 5:
Get the sum of the first two terms
STEP 6:
Repeat until i<=n
Z = x + y
Print z
x = y, y = z
i = i + 1
STEP 7:
Stop
Code implementation with Javascript
//program to write fibonacci algorithm
function fibonacci_search(num)
{
var x = 1,
y = 0,
z;
while (num >= 0)
{
z = x;
x = x + y;
y = z;
num--;
}
return y;
}
document.write(fibonacci_search(8))Code implementation with Python
# Fibonnacci sequence solution
def fibonacci(no): #the base
case
if no <= 1:
return no
else :
return (fibonacci(no - 1) + fibonacci(no - 2))
length = int(input("Length of the sequence "))# takes input from the user
if length <= 0:
print("Please enter a number greater than zero")
else :
print("Fibonacci sequence:")
for i in range(length):
print(fibonacci(i))
# output
# Length of the sequence 10# Fibonacci sequence:
# 0,1,1,2,3,5,8,13,21,34Jump Search Algorithm
Jump search, like binary search, works only with sorted arrays and uses a divide and conquer approach, designed as an improvement over linear search. The algorithm searches for an element by jumping m number of components and determines if the searched term is between the previous and current jump.
To start the process, we need a low and high value, namely, the starting and ending points of the array. The algorithm also has a size n, the size of the array, and a block jump or size m.
If we have an array of 1 - 12 (making the size n = 12), with index 0 to 11, our low value is 1, which is at index 0, and the high value is 12, which is at index 11. If we take our jump block, m, to be 3, the algorithm iterates by jumping over every three elements. So it moves from index 0 - 3, jumps from 3 to 6, and 6 to 9.
At every jump, we compare the elements in the array with the target element and array’s size. We also note the number of jumps the program makes.
Between 0-3, 1 jump
Between 3 - 6, 2 jumps
Between 6 - 9, 3 jumps
Here, it stops. Jumping from 9 - 12 is smaller than the jump size (which is 3). Our last index stops at 11. From index 9, we perform the search linearly, moving from 9 to 10 to 11. This linear movement is still counted as a jump but not of block m. therefore the total number of jumps = 5.
The time Complexity, O(√n) is calculated by the number of jumps and the number of elements within each block.
Related Articles
Algorithm
STEP 1:
Start
STEP 2:
Determine jump size, m with the formular, math.sqrt(n(arr))
STEP 3:
Start iteration at the beginning of n
STEP 4:
When i = 0, start iteration with m jump. Do this until the end of the list (n < i)
STEP 5:
Compare the target element with elements in the list after each jump.
IF target element == TRUE
STEP 10
STEP 6:
IF target element less than m, continue jump
STEP 7:
IF target element greater than jump
Stop at the previous jump and perform a linear search
STEP 8:
IF m jump cannot be completed, but there are elements in n, perform a linear search
STEP 9:
IF target element == FALSE,
Exit
STEP 10:
Exit
Code implementation in JavaScript
function jumpSearch(n, element)
{
let len = n.length
//making m the jump block
let m = Math.floor(Math.sqrt(len));
//starting index
let startindex = 0,
currentStep = m;
while (n[Math.min(currentStep, len) - 1] < element)
{
//processing to the next jump if target element not found in the current jump
startindex = currentStep;
currentStep += m;
if (startindex >= len) return -1;
}
//Linear Search block
while (n[startindex] < element)
{
startindex++;
//if we can't find target element in the array
if (startindex == Math.min(currentStep, len)) return -1;
}
if (n[startindex] == element) return startindex
else return -1;
}
let n = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
let element = 12;
document.write(jumpSearch(n, element))Code implementation in Python
import math
def jump_search(n, element):
#n - The array / list
# element - Item that the index needs to find
print("Processing Jump Search")
a = len(n)
m = int(math.sqrt(a))# m = jump block
i = 0
while i != len(n) - 1 and n[i] < element:
print("Processing Batch - {}".format(n[i: i + m]))
if n[i + m - 1] == element:
return i + m - 1
elif n[i + m - 1] > element:
B = n[i: i + m - 1]
return linear_search(B, element, i)
i += m
B = n[i: i + m]
print("Processing Batch - {}".format(B))
return linear_search(B, element, i)The Linear Search function part of the code
def linear_search(B, element, loc):
#loc - The Index where the remaining batch begins# B is the derived list
print("\t Starting Linear Search")
i = 0
while i != len(B):
if B[i] == element:
return loc + i
i += 1
return -1
if __name__ == "__main__":
print(jump_search(n, 12))
# prints the indexSublist Algorithm
The sublist search algorithm determines if there is a sublist in another list. It compares the first list to the second to ascertain if list one is in list two.
If we had a list containing [25, 12, 19, 2] and another that had [14, 25, 33, 12,2, 80, 19, 72], we could immediately see some shared elements. What the sublist algorithm does is to check this in a linear, sequential manner.
Algorithm
STEP 1:
Start
STEP 2:
Declare the variables for the two lists
STEP 3:
Take first node of the second list
STEP 4:
Match the elements of the first list with this node
STEP 5:
IF the elements match, return TRUE
STEP 6:
ELSE, iterate through the first node
STEP 7:
AND take the second list to the second node
STEP 8:
Repeat the process until both lists are empty
STEP 9:
IF the first list becomes empty,
Return 'List not found'
STEP 10:
Exit
Code implementation with JavaScript
// JavaScript program to find a list in second list
// A Linked List node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
// Returns true if first list is present in second list
function findList(list1, list2)
{
var ptr1 = list1,
ptr2 = list2;
// If both linked lists are empty,return true
if (list1 == null && list2 == null) return true;
// Else If one is empty and other is not, return false
if (list1 == null || (list2 != null && second == null)) return false;
// pick nodes one by one
while (list2 != null)
{
// Initialize ptr2 with
// current node of second
ptr2 = list2;
while (ptr1 != null)
{
if (ptr2 == null) return false;
else if (ptr1.data == ptr2.data)
{
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// If not equal then break the loop
else break;
}
// Return true if first list gets traversed
if (ptr1 == null) return true;
// Initialize ptr1 with first again
ptr1 = first;
// move to the node of second list
second = second.next;
}
return false;
}
/* Function to print the nodes */
function printNode(node)
{
while (node != null)
{
document.write("%d ", node.data);
node = node.next;
}
}
// The function we need to add new node to linked lists
function newNode(key)
{
var temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// Driver Code
/*
Let us create two linked lists to test
the above functions. Created lists
shall be x: 1->2->3->4 y: 1->2->1->2->3->4
*/
var x = newNode(1);
x.next = newNode(2);
x.next.next = newNode(3);
x.next.next.next = newNode(4);
var y = newNode(1);
y.next = newNode(2);
y.next.next = newNode(1);
y.next.next.next = newNode(2);
y.next.next.next.next = newNode(3);
y.next.next.next.next.next = newNode(4);
if (findNode(x, y) == true) document.write("LIST FOUND");
else document.write("LIST NOT FOUND");Code implementation with Python
#Python3 program to find a list in another list
class Node:
def __init__(self, value = 0):
self.value = value
self.next = None
# Returns true
if first list is present in second list
def findList(list1, list2):
if not first and not second:
return True
# If ONLY one of them is empty, #
return False
if not list1 or not list2:
return False
ptr1 = first
ptr2 = second
# Iterate the second list by picking nodes one after the other
while ptr2:
#Initialize 'ptr2'
with current node of 'second'
ptr2 = second
while ptr1:
if not ptr2:
return False
elif ptr1.value == ptr2.value:
ptr1 = ptr1.next
ptr2 = ptr2.next
else:
break
# If 'ptr1' is None / empty, that means the 'first LL' has been completely traversed and matched so return True
if not ptr1:
return True
return FalseInterpolation Search Algorithm
The interpolation algorithm is another divide-and-conquer algorithm. It works with a sorted array of uniform distribution.
Unlike the other algorithms, it does not just start a search. Instead, it has a mathematical formula and performs some calculations to determine where to begin that search.
Two conditions are necessary for this algorithm to perform
- The elements must be sorted
- The elements of the list must be uniformly distributed. The difference between the elements must be the same.
The formula to get a starting position:
Where,
low is the starting index value
x is the searched element
a is the values of the indexes
High is the last index value of the array
If we have an array of the following values
[1, 4, 7, 10, 13, 16, 19, 21, 24] with a uniform difference of 3, and we need to find 16, here is how we go about it.
Low = 0
High = 24
x = 16
a[l] = 1
a[h] = 26
16 is at index 5. It has taken just one step to find 16.
Sometimes, we might have a large array that is slightly not uniformed. This won't give a perfect answer. We will need to readjust the values of…
The time complexity is 0(log n) when values are uniformly distributed as 0(n), for worst-case when values are not evenly distributed.
Algorithm
STEP 1:
Start
STEP 2:
Declare the variables. x = target element
STEP 3:
Write the formula to calculate the value of the index
STEP 4:
If the value of the x and index == True, the index is returned.
STEP 5:
If the value is less than the index,
THEN the value of the index is recalculated with adjusted values for the left sub-array
STEP 6:
If the value is higher than the index,
THEN the value of the index is recalculated with adjusted values for the right sub-array.
STEP 7:
If value of x and index == FALSE
RETURN 'Index not found'
STEP 8:
Exit
Code implementation with JavaScript
//Interpolation code javascript
const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const index = 25;
const interpolation_Search = (arr = [], index) =>
{
let l = 0;
let r = arr.length - 1;
while (l <= r)
{
const a_r = arr[r] - arr[l];
Const a = r - l;
const x = index - arr[left];
if (x < 0)
{
return -1;
}
if (!a_r)
{
return arr[l] === index ? l : -1;
}
const middleIndex = l + Math.floor((x * a) / a_r);
if (arr[middleIndex] === index)
{
return middleIndex;
}
if (arr[middleIndex] < index)
{
l = middleIndex + 1;
}
else
{
r = middleIndex - 1;
}
};
return -1;
};
console.log(interpolation_Search(arr, index));Code implementation with Python
#program to write interpolation search
def Interpolation_search(arr, index):
low = 0
high = (len(arr) - 1)
while low <= high and index >= arr[low] and index <= arr[high]:
element = low + int(((float(high - low) / (arr[high] - arr[low])) * (index - arr[low])))
if arr[element] == index:
return element
if arr[element] < index:
low = element + 1;
else :
high = element - 1;
return -1
print(Interpolation_search([1, 2, 3, 4, 5, 6, 7, 8], 6))Conclusion
We hope we’ve given you some good case on how to use Search Algorithms and have mentioned the most popular in their respective JavaScript and Python implementation. Search algorithms are integral part of Algorithmic knowledge in Software Engineering – and the ‘have to know’ for every software engineer!
