DIFFERENT SEARCHING ALGORITHMS
INTRODUCTION
In computer science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values.
From the apps on your phone to the sensors in your wearables and how posts appear in your Facebook News Feed every site has it’s different working algorithm. One will be pushed to find a service that isn’t powered by some form of algorithm.
Search algorithms form an important part of many programs. Searching algorithms is a basic, fundamental step in computing done via step-by-step method to locate a specific data among a collection of data. We can choose from numerous search types, and select the algorithm that best matches the size and structure of the database to provide a user-friendly experience.
Let us now dive into different types of searching algorithms:-
LINEAR SEARCH:
➢Searching is useful to find any record stored in the file.
➢Searching books in library
For that we have two searching algorithms:
➢Linear Search/Sequential Search
➢Binary Search
How does it work ?
Linear search is the basic search algorithm used in data structures. It is also called as sequential search. Linear search is used to find a particular element in an array. It is not compulsory to arrange an array in any order (Ascending or Descending) as in the case of binary search.
Input: Array A of n elements
Output: Return index/position of the element X in the array A
Two Cases:
Either element is present : Linear Search Gives the Index
Or elements not present: Elements not found
ITERATIVE IMPLEMENTATION FOR LINEAR SEARCH
#include<iostream>
using namespace std;
int Linear_search(int A[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (A[i] == x)
return i;
return -1;
}
int main(void)
{
int A[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(A) / sizeof(A[0]);
int result = Linear_search(A, n, x);
if (result == -1)
cout<<”Element is not present in array”
else
cout<<”Element is present at index “ <<result;
return 0;
Time and Space Complexity of Linear Search
• Best case what is the minimum number of comparisons that can be done for n items =
comparisons: 1
• Occurs when x is the first element examined
• Worst case what is the maximum number of comparisons for n items= comparisons: n
• Case 1: x is the last element examine
• Case 2: x is not in the list
• Average case on average, how many comparisons do you expect the algorithm to do
• This is bit tougher because it depends on
• The order of the elements list
• The probability that x is in the list at all
BINARY SEARCH:
This type of searching algorithms is used to find the position of a specific value contained in a sorted array. Binary search algorithm works on the principle of divide & conquer and it is considered the best searching algorithms because of its faster speed to search ( Provided the data is in sorted form).
How does it work ?
In its simplest form, Binary Search operates on a contiguous sequence with a specified left and right index. This is called the Search Space. Binary Search maintains the left, right, and middle indices of the search space and compares the search target or applies the search condition to the middle value of the collection; if the condition is unsatisfied or values unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with an empty half, the condition cannot be fulfilled and target is not found.
ITERATIVE IMPLEMENTATION OF BINARY SEARCH
#include <iostream.h>
using namespace std;
int binary_search(int A[], int l, int r, int x)
{
while (l <= r) {
int mid = (l + r)/ 2;
if (A[mid] == x)
return mid;
if (A[mid] < x) // If x greater, ignore left half
l = mid + 1;
else // If x is smaller, ignore right half
r = mid — 1;
}
return -1; // if we reach here, then element was not present
}
int main(void)
{
int A[ ]={5, 12, 23, 42, 64, 78};
int x = 35;
int n =sizeof(A) / sizeof(A[0]);
int result = binarySearch(A, 0, n — 1, x);
if(result == -1)
cout << “Element not found in the array“
else
cout << “Element found at “ << result;
return 0;
}
TIME COMPLEXITY OF BINARY SEARCH
The time complexity of the binary search algorithm is O(log n). The best-case time complexity would be O(1) when the central index would directly match the desired value. The worst-case scenario could be the values at either extremity of the list or values not in the list.
MEDIAN SEARCH
The median-of-medians algorithm is a deterministic linear-time selection algorithm.
HOW DOES IT WORKS?
The algorithm works by dividing a list into sublists and then determines the approximate median in each of the sublists. Then, it takes those medians and puts them into a list and finds the median of that list. It uses that median value as a pivot and compares other elements of the list against the pivot. If an element is less than the pivot value, the element is placed to the left of the pivot, and if the element has a value greater than the pivot, it is placed to the right. The algorithm recurses on the list, honing in on the value it is looking for.
Example: 7 10 4 3 20 15 8 12 6
randomly choose an element a = 10
Now divide the array into three part S1, S2, S3
S1= {7,4,3,8,6}
S2={10}
S3={20,15,12}
Now length of (S1)>=k=5>4 first condition true select(4,S1)
Check in the array S1={7,4,3,8,6}
Randomly choose element a=3
Now divide the array S1 into three parts S11,S12,S13
S11={}
S12={3}
S13={7,4,8,6}
Here first and second condition fail third condition true select(3,S13)
Find the k=4th median
Here k=3
S13= {7,4,8,6}
Randomly choose a=7
Now divide S13 into three parts such as: S131,S132,S133
S131={4,6}
S132={7}
S133={8}
Here condition 1 fail
Condition 2 true
Length(S1)+length(S2)>=K 3==3
Return median a =7
TIME COMPLEXITY OF MEDIAN SEARCH
The median-of-medians algorithm runs in O(n) time
