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.
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.
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.
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.
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.
Top comments (21)
Well explain Suraj,
Currently learning Java DSA - shorturl.at/fEFIW
Thanks for sharing helpful resources!
Nice visualisations
Yep, but the credit for visualisation is from different websites.
Noted. Where did you get em
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.
I think you should've mentioned in a line about how DFS and BFS use stack and queue for searching the nodes
Nice post! I think it would be really good if you presented the average / best / worst O-notation complexities of the algorithms as well :)
Such a great list! I'll will love to learn all these algos ❤️
Thanks for putting everything together into an easy to digest format 🔥
It's my pleasure that you like the post.
Very good, nice choice of visualistations
Nice post! :D
Thank you
Great refresher đź‘Ť
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.