DEV Community

Cover image for Algorithms Every Programmer Should Know
Suraj Vishwakarma
Suraj Vishwakarma

Posted on • Updated on • Originally published at surajondev.com

Algorithms Every Programmer Should Know

Introduction

Hello Guys, Today I am going to start a series named "Algorithm Every Programmer Should Know." In this series, we are going to look into various algorithms such as Searching, Sorting, Graphs, Array, etc.

Today starting with the very first part of the series with the Searching Algorithm. We are going to look into 4 searching algorithms that every programmer should know. Now let's Started.


Linear Search

In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.

Linear Search

In linear search, we search for the target element in the list in sequential order one by one from the first element of the list to last.

Best Case: Target Value is at the first position of the list

Worst Case: Target Value is the last position of the list

When to use:

  • When the list is unsorted
  • When the list is small

Binary Search

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value.

Binary Search

In Binary Search, the list must be in some sorted order. We searched the target value by picking the value from the middle of the list and comparing it. If not matched, then if the target value is less than the middle element then the initial half will be drop otherwise the terminating half will be drop. The process will continue until we find the target value.

Best Case: Target Value is at the middle position of the list

Worst Case: Target Value is at either first or last position of the list

When to use:

  • When the list is sorted
  • When the list is big

Depth First Search(DFS)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

Depth First Search(DFS)

In DFS, we choose the root of the graph, tree, or data structure and explore every branch in order. When a branch is selected then it explores its all sub-branches before changing to a different branch.

Best Case: Target Value is at the root position of the tree

Worst Case: Target Value is at the tip of a sub-branch of the last ordered branch

When to use:

  • When the tree is very wide
  • When the target value is located at the deep of the tree

Breadth First Search(BFS)

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Breadth First Search(BFS)

In BSF, same as in DFS, we choose the root node of graph, tree, or data structure. After node, we move to its all adjacent node and then to the next level that is all node adjacent to the branch.

Best Case: Target Value is at the root position of the tree

Worst Case: Target Value is at the tip of the longest branch of the tree

When to use:

  • When the target value is not far from the root of the tree
  • When the tree is very deep, and the target value is rare.

Last Note

Thank You for reading the blog post and I hope you enjoy it too. I will back soon with the next part of the series.

Discussion (20)

Collapse
chidioguejiofor profile image
Chidiebere Ogujeiofor

Nice visualisations

Collapse
surajondev profile image
Suraj Vishwakarma Author

Yep, but the credit for visualisation is from different websites.

Collapse
chidioguejiofor profile image
Chidiebere Ogujeiofor

Noted. Where did you get em

Collapse
kaelscion profile image
kaelscion • Edited on

This is a great post. I actually like that you didn't go into "here's how you do each algo in...". I know that sounds weird, but I find examples of how to perform each algo can get overwhelming and confusing, especially when the example language isn't one I speak. Like "Now I'll show you how to do this in Rust" and I'm like "C#, Python or maybe JS I would have understood. Unfortunately, these examples are relatively lost on me." Also, explaining the algo in "high-level" terms rather than demonstrating them gets me to think about how my I'd implement them in my day-to-day language, which is what this is all about: figuring things our for yourself. That, for me, is the only way it really sticks. Great job! And the "advantages/disadvantages" is a nice touch. Algorithmic thinking is such an essential skill, but also a very difficult one to truly master.

Collapse
sudonitin profile image
Nitin Sahu

I think you should've mentioned in a line about how DFS and BFS use stack and queue for searching the nodes

Collapse
kubukoz profile image
Jakub Kozłowski

Nice post! I think it would be really good if you presented the average / best / worst O-notation complexities of the algorithms as well :)

Collapse
mindninjax profile image
Rishabh Singh ⚡

Such a great list! I'll will love to learn all these algos ❤️
Thanks for putting everything together into an easy to digest format 🔥

Collapse
surajondev profile image
Suraj Vishwakarma Author

It's my pleasure that you like the post.

Collapse
levirs565 profile image
Levi Rizki Saputra

Great post!

Collapse
jaswindersingh1903 profile image
Jaswinder Singh

Great refresher 👍

Collapse
zediwards profile image
ZediWards

Thanks for the great post!!!
Explanation structure is great. Didn't make me feel overwhelmed and finished the article knowing a lot more than when I started.

Collapse
alimobasheri profile image
MirAli Mobasheri

Great and useful descriptions of the concepts. Thanks!

Collapse
seba2020 profile image
Sebastian Hondarza G

Nice post! :D

Collapse
surajondev profile image
Suraj Vishwakarma Author

Thank you

Collapse
vijayvenkatanarayan profile image
VijayVenkataNarayan

good explanation with diagrams! Thanks

Collapse
surajondev profile image
Suraj Vishwakarma Author

Happy to help you

Collapse
marciobbarbosa profile image
marcio bernardes

nice, thank you

Collapse
rtorsoli profile image
Riccardo Torsoli

Cool.

Thanks

Collapse
subham3112 profile image
subham3112

crisp explaination

Collapse
frameworkz profile image
frameworkz

Very good, nice choice of visualistations