Sources Contact Advanced Search Tutorials

An Interest In:

Web News this Week

Search Archive

Some of Our Sources

View All Sources

Help Webnuz

Referal links:

September 29, 2021 06:06 pm GMT

Algorithmic Approach to Problem Solving

Searching Algorithms

Searching is an algorithm which is widely used in programming.

It is a type of algorithm which is used to check for an element or get some information about the element in a particular data structure like arrays or linked list.

The region where we need to look for a particular element ( i.e whether an element is present or not ) is called the search space. For instance, in case of an array the search space is defined as the entire array or the two indices of the array within which searching needs to take place.

Types of Searching Algorithms

There are various types of algorithms but we will stick to the most commonly used searching techniques and we will find out the most optimised way of searching in terms of time complexity.

Linear Search

Linear Search or Sequential search as the name suggests is a type of searching algorithm where we look for an element in a sequential manner by traversing the search space i.e in a particular order.

Approach to the above algorithm

  1. Given an array (for simplicity) and a target element.   2. Traverse the entire array starting from the left most index till the end and check whether the target element matches     with the current element at a particular index of an array.  3. Return the index of the element if found in the array otherwise return -1 .

Source - https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorithm.htm

Code sample in C++

//Implementation of Linear Search/*By Pratyaksh Khurana GWOC'21 Contributor*/#include<bits/stdc++.h>using namespace std;int fun(int arr[],int size,int key){  // if the size of the array is 0, means array does not exist and straight away return -1  if(size == 0)             return -1;  // traversing the entire array by placing a check and comparing with the key (i.e target)  for (int index = 0; index < size; index++)  {    if(arr[index] == key)      return index;       // returns the index of the element if found   }  // means element not found so return -1  return -1;}int main(){  int size,target;  cin>>size>>target; // taking input from the user, size of the array and the target element  int arr[size];  // inserting elements in the array  for (int index = 0; index < size; index++)    cin>>arr[index];  int x = fun(arr,size,target);  // function call that returns the index of the element                               // if not found returns -1   if(x == -1)   cout<<"Element not found";  else    cout<<"Element is found at index "<<x;    return 0;}

Test case 1

  Input  5 23  9 20 65 23 32  Output  Element is found at index 3

Test case 2

  Input  7 1011  77 65 98 12 32 44 951  Output  Element not found

Time Complexity Analysis in case of Linear Search

Time complexity is the time taken by an algorithm as a function of length of input.

In simple words it is the number of comparisons that we need to make.

In the worst case the time complexity of the above algorithm is O(n) , where n is the size of the search space
( i.e in our case it is the size of the array).

In the best case the time complexity of the above algorithm is O(1) , in this case the element will be present at the 0th index of
the array.

Binary Search

Binary Search algorithm deals with the intervals and it divides the search space in two parts, and it must fufill the condition that the search space must be sorted
(i.e in increasing or decreasing order).

In this case start from the whole search space (sorted array for simplicity) and find the middle element of the search space and then compare whether the target element
is equal to middle element or not, if the target element is less than the middle element then reduce the search space to the left else shift it to the right and if the
target element matches with the middle element then return the index of the element.

Approach to the above algorithm

  1. Given an array (must be sorted in increasing order) and a target element.  2. Take two pointers (say start and end) where start pointer is at the 0th index of the array and the end pointer is at the     last index of the array.   3. Find the middle element of the array (say mid), and compare it with the target element.  4. If the target element = middle element, return the index.  5. If the target element > middle element, shift the start pointer to (start = mid + 1).    6. If the target element < middle element shift the end pointer to (end = mid - 1).In case of decreasing order manipulate the pointers accordingly.

Source - https://brilliant.org/wiki/binary-search/

Code sample in C++

//Implementation of Binary Search/*By Pratyaksh Khurana GWOC'21 Contributor*/#include<bits/stdc++.h>using namespace std;//If the search space is sorted in increasing orderint IncreasingBinary(int *a,int n,int target,int start,int end){  while(start <= end)  {    int middle = start + (end-start)/2;     // the above mentioned formula is used so that (start + end) does'nt overflows the range of int datatype    if(a[middle] == target)     return middle;    else if(a[middle] > target)     end = middle - 1;    else if(a[middle] < target)     start  = middle + 1;    }  return -1; //if not found return -1}//If the search space is sorted in decreasing orderint DecreasingBinary(int *a,int n,int target,int start,int end){  while(start <= end)  {    int middle = start + (end-start)/2;    // the above mentioned formula is used so that (start + end) does'nt overflows the range of int datatype    if(a[middle] == target)     return middle;    else if(a[middle] < target)     end = middle - 1;    else if(a[middle] > target)      start = middle + 1;  }  return -1;  //if not found return -1}int main(){  int size,target; //size of the array and the target element  cin>>size>>target;  int a[size];   //declaring the array  for (int index = 0; index < size; index++)    cin>>a[index];  //to check whether the array is sorted in increasing / decreasing order  if(a[0] <= a[size-1])  {   int idx = IncreasingBinary(a,size,target,0,size-1);   cout<<idx;     // index of the element   }  else if(a[0] >= a[size-1])  {    int idx = DecreasingBinary(a,size,target,0,size-1);    cout<<idx;  }   return 0;}

Test case 1

  Input5 3
  2 3 4 7 10
Output
1

Test case 2

  Input7 88
  130 99 89 88 56 12 2
Output
3

Test case 3

  Input6 34
  12 44 98 103 540 900
Output
-1

Time Complexity Analysis in case of Binary Search

The time complexity of the above algorithm is O(log(n)), where n is the size of the search space (say array of size n).

Comparison between Linear Search and Binary Search Algorithm

Time complexity in case of Linear Search (talking about the worst case) is O(n).

Time complexity in case of Binary Search (talking about the worst case) is O(log(n)) which is far more optimised as compared to linear search and it can reduce the
comparisons at a faster rate as it is a logarithmic time complexity.

Practice Problems on the above mentioned algorithms

Practice problems on various coding platforms like HackerRank, HackerEarth, and Leetcode to get comfortable with the application part.

ProblemSet on Searching Algorithms

 https://www.hackerearth.com/practice/algorithms/searching/linear-search/practice-problems/
 https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/
 https://leetcode.com/tag/binary-search/

Happy Coding !!

Original Link: https://dev.to/pratyaksh1610/algorithmic-approach-to-problem-solving-2f0

Share this article:

View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To