DEV Community

Cover image for Simple search vs Binary search Algorithms.
Olasunkanmi Igbasan
Olasunkanmi Igbasan

Posted on • Updated on

Simple search vs Binary search Algorithms.

Hello there !
Welcome and stay with me as I explain Big O Notation to you in the simplest words ever!

"Total time needed for an algorithm to run," is the simplest definition of Big O Notation, but why does it matter to you as a developer?

To answer that, below is a simple search Algorithm that finds any given item in an array; if the given item is not in the array, our algorithm returns null.

Simple Search Algorithm.

Image description

           Fig 1.0 (For-loop search algorithm )
Enter fullscreen mode Exit fullscreen mode

The above is a simple JavaScript For-loop that iterates over each item in the array, checks if the current iteration equals our input ('item' ), and if the item is not in the array, it returns "null."

Below (Fig 2.0 ) is a while loop that does the same as the above For-loop.

Binary Search Algorithm.

Image description

      Fig 2.0 (while loop search algorithm )
Enter fullscreen mode Exit fullscreen mode

Although, the above functions do precisely the same thing. But what happens when the number of items in our array increases exponentially?

How efficient will both our algorithms still be ?

A step-by-step break-down of the Binary Search Algorithm:

  1. We compare 'item' with the middle index of the array.
  2. if 'item' matches the mid index, we return the mid element.
  3. else if 'item' is greater than the middle element, length of the array is reassigned to the middle ( element - 1 ).
  4. else if 'item' is lesser than the middle element, beginning of the array is reassigned to the middle ( element + 1 ).

With this method we eliminate half of the array in the first comparison.

For better understanding,
If the length of the array increases to 1millon.
With the first function (Fig 1.0), we will perform 1 million iterations (worst case) to find our item. However, we will perform at most 10 iterations (worst case) with the second function.

The Big O notation of our functions.

Simple search algorithm (Fig 1.0) - O(n) // Bad guy
Binary search algorithm (Fig 2.0) - O(log n) // Good guy.

Stay with me on this blog while I explain Algorithms and Data Structures as succinctly as possible.

Link to Code and remember to give it a star.
https://github.com/Olatisunkanmi/Data-Structures-and-Algorithms-/tree/main/5%20Algorithms/Binary%20Search

Top comments (13)

Collapse
 
jhhornn profile image
Awosise Oluwaseun

Nice write up

Collapse
 
pauldumebi profile image
Paul Dumebi

Interesting. I learnt something

Collapse
 
temijei profile image
Victoria Ajibola

This was super helpful πŸ‘πŸ½

Collapse
 
tobisam2000 profile image
Oluwatobiloba Adesokan

Nice one ☺️

Collapse
 
mavludin profile image
Mavludin

Thanks for the article.

One thing I would like to point out is that to be able to apply the binary search, we must have a sorted array.

Collapse
 
olatisunkanmi profile image
Olasunkanmi Igbasan

Yes.

Collapse
 
modupe_okaseun_0983b25a0f profile image
Modupe Okaseun

This is an amazing write up, nice one!

Collapse
 
olatisunkanmi profile image
Olasunkanmi Igbasan

Thank you πŸ“

Collapse
 
qreamville profile image
Balikis Moromoke Oyeleye

Amazing write-up πŸ‘

Collapse
 
olatisunkanmi profile image
Olasunkanmi Igbasan

Thank you

Collapse
 
realsteveig profile image
STEVE

Good read..πŸ’ͺ

Collapse
 
ayhoung profile image
Allen Houng

shouldn't simple search be O(n)? O(1) is constant time

Collapse
 
olatisunkanmi profile image
Olasunkanmi Igbasan

Thank you so much, totally!