Data Structures & Algorithms

I took a long holiday, and when I went back to the university, I felt really bad about myself. During the DSA lecture, I realized that I didn’t understand many of the things being taught. My friends had already covered some algorithms, so I didn’t know most of what the lecturer was explaining.

First, he gave an introduction to the module, and then suddenly he moved on to Bubble Sort. I think he should have explained Linear Search and Binary Search first. In the first semester, another lecturer had covered those topics, but I don’t want to miss including these in my article.

First of all, what is an algorithm? Just think like this: when you wake up early in the morning, there are certain routines you follow. You get up from the bed, go to the washroom to brush your teeth, then have your morning tea and breakfast. This is also an algorithm.

However, most people think algorithms are something that only mathematics experts understand. That is one of the biggest mistakes you can make in your life.

Everyone knows about algorithms, but many people keep following the same algorithms in their lives for years. That is one reason they remain in the same place haha!

By the way, in programming, algorithms simply tell the machine how to solve real world problems. We must execute them step by step, and the steps need to be clear and simple, just like in this article.

However, there is a more formal definition of an algorithm:

“An algorithm is a finite, step by step set of instructions or rules followed to solve a specific problem, perform a computation, or complete a task.”

In programming, algorithms can be represented using flowcharts, pseudocode, or programming languages. Nowadays, we also describe algorithms using natural language.

There can be many algorithms for the same problem. So how do we identify the best one? Think about it like this imagine you have three good friends. One is very handsome, another is strong, and the last one is a talented musician.

If you are in trouble with someone, whom would you call? From my perspective, I would call the strong one. If I am feeling stressed, I would call my musician friend. If I need advice about a girl, I would call my handsome friend. That means I need all three of them — but depending on the situation, one may be more suitable than the others.

Algorithms are similar. For one problem, there may be different algorithms. But depending on the situation, one algorithm may be more suitable than the others. However, first of all, an algorithm must work otherwise haha!

A good algorithm should

• Work correctly
• Be simple enough for people to understand
• Be efficient

These kinds of algorithms can be called great algorithms.

So why do we need algorithms? Every calculation we perform requires an algorithm. In data processing, we need algorithms. In fact, we need algorithms for almost everything even if we don’t always realize that what we are using is actually an algorithm.

In algorithms, there are several common categories such as sorting algorithms, searching algorithms, and algorithms in action. I think we should first discuss searching algorithms because they are easier to understand than the others hehe!

Searching Algorithm

Just imagine you are the lecturer of our class, and some students have signed in for their friends. You now have their index numbers. What would you do? Would you search for each student one by one on the website, or would you use a faster method? That is why we need search algorithms.

A search algorithm can be defined as:

“A step by step procedure used to find a specific item or value within a collection of data.”

There are two main types that we usually use

1. Linear Search
2. Binary Search

But there are some others like

1. Interpolation Search
2. Jump Search
3. Hashing
4. A* Search Algorithm
5. Graph Traversal Algorithm

Linear Search

Linear search is sometimes called sequential search. Imagine your friend asks you to guess a number between 1 and 100, and he promises to tell you when you get it right. If he could do it in just one try, he must be a magician! Otherwise, he would need to check more than once.

Get Lasith Eeshan’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In linear searching, we start from one and increase the number one by one. Eventually, we will definitely get the answer unless, of course, your friend is lying to you, hehe.

Linear search is fine for finding an answer, but when it comes to time, it can be horrible. Just imagine if the number was 100 you’d have to guess a hundred times! Haha.

“Linear searching works sequentially checking each element in the dataset one by one until a match is found or the entire list has been searched. ”

Linear search starts from index 0 of the array or list and compares the target value with the current element. If it matches, the algorithm returns the index of that element. If not, it moves to the next element and repeats the process. If the end of the array is reached without finding the target, the algorithm returns that the target wasn’t found.

An important concept here is algorithm complexity, which includes time complexity and space complexity. In this case:

• Worst-case time complexity: O(n) — when the target is at the end or not present.
• Best-case time complexity: O(1) — when the target is at the beginning.
• Average-case time complexity: O(n) — considering the target could be anywhere.

These are simple and easy to understand, and they work for both sorted and unsorted data structures. The space complexity is O(1) because no additional memory is required. However, for larger datasets, linear search becomes inefficient.

Binary Search

Let’s continue with an example. Suppose your friend has to guess the number you selected, say 37. When he suggests a value:

• If it’s the target, you say “Stop!”
• If it’s higher than your number, you say “High”
• If it’s lower than your number, you say “Low”

Using this feedback, your friend can guess smarter. For example, he might start with 50 (the midpoint of 1 and 100). You say “High”, so he knows the number is lower. Next, he guesses 25 (midpoint of 1 and 50). You say “Low”, and he continues this process until he finds 37.

This approach reduces the search range each time using a smart logic, which is much faster than guessing one by one. However, if the data is unsorted or you don’t provide the high/low feedback, this method won’t work.

“ For sorted array repeatedly dividing the search space in half until the target value is found or the search space is empty. ”

In here we are using divide and conquer principal.

This method works only for sorted arrays. The time complexity is O(log n), which makes it much faster than linear search.

We initialize the lower pointer at index 0 and the higher pointer at index (n − 1), assuming the array is sorted in increasing order. Then we repeatedly check the middle element and reduce the search range based on whether the target is smaller or larger than the middle value.

Binary search is commonly used in standard library functions in languages like Java, C++, and Python.

#include <iostream> 
#include <sstream>
#include <vectors>
using namespace std;

void binary_search(vector<int> need_to_sort,int target){
  int low=0;
  int high=need_to_sort.size()-1;
  int point =(high+low)/2;
  int current_value=need_to_sort[point];
  while (current_value!=target){
    if (current_value>target){
      high=point;
      point=(high+low)/2;
    }
    else{
      low=point;
      point=(high+low)/2;
    }
    current_value=need_to_sort[point];
  }
  if (current_value==target){
    cout<< "Target value: "<<target <<" is found at index "<<point;
  }
  else{
    cout<<"Target value is not in the array";
  }
}

int main(){
  int number;
  int target;
  cout<<"Sorted array with split by space: " ;
  cin >> number;
  cout<<endl;
  cout<<"Target value";
  cin<<target;
  vector<int> array(number);
  cin.ignore();
  int integer;
  string input_line;
  if (getline(cin,input_line)){
    stringstream ss(input_line)
    while(ss>> integer){
      array.push_back(integer);
    }
  }
  binary_search(array,target);
  return 0;
}

I think we have learned a lot in this article. By now, you probably have a clear idea of what an algorithm is. We also moved forward and discussed searching methods, along with the key features of Linear Search and Binary Search.

I would love to include sorting algorithms and go deeper into time complexity as well. However, if I were the reader, I might not want to read a very long article all at once.

So, I’ll stop here for now.

Stay tuned for the next part, where we’ll explore sorting methods and complexity in more detail!

Have a nice day 🖐…