Forem: Nemwel Onsando

Big O Notation in Javascript

Nemwel Onsando — Fri, 01 Jul 2022 01:00:48 +0000

Big O Notation is a very important computer science concept that all developers should understand, because If you don’t, you could end up writing some very inefficient functions at the wrong time, resulting in a poor performing program.

What are your thoughts? Find out more here

Data Structures and Algorithms 102: Javascript Binary Search Algorithm

Nemwel Onsando — Fri, 01 Jul 2022 00:36:04 +0000

Introduction

In my previous article Data Structures and Algorithms 101 you can read an introduction to what is data structures and algorithms.

In this article I will deep dive into Binary search algorithm. Searching algorithms falls into either sequential or interval search.Linear and binary searches are the commonly two simple as well as easy to implement algorithms.

Binary search is faster than linear search(where search is done in a sequence on every element). Here, am going to walk you through binary search algorithm and:

define what is a binary search
how to implement it
where it can be used

What is binary search algorithm?

Binary search algorithm is a divide-and-conquer algorithm that divides elements in a sorted array roughly into half every time it checks for the target element we are searching.Simply put,we divide the problem into simpler problems until it becomes simple enough to solve them directly.

How do we implement a binary search?

You can implement most of the algorithms in two ways:

Iteratively or
Recursively

Iterative version of the algorithm involves a loop which repeats some steps until the stopping condition is met whereas recursive version uses a function that calls itself. I will be covering iterative version in this article.

We begin by implementing a function in JavaScript that search element value and returns its index:

       const binarySearch = (elements, value) => {
       // Add other code

          }

Assuming we have a sorted array,set the lower(startIndex) and upper(endIndex) boundaries at the appropriate ends of the sequence:

 const arr =  [0,5,12,23,34,35,46,47,58];
 const binarySearch = (elements,value) => {    
       let startIndex = 0;
       let endIndex = arr.length - 1;

         }

Now we will identity the middle element to see if it has the value we want to search.We calculate this middle value (middleIndex) by taking the average of both boundaries:

   let middleIndex = Math.floor((startIndex + endIndex) / 2 );

Here, you notice I have used the Math.floor() function to help handle an odd and even number of element in the bounded range by flooring the result.

Now,we compare that middle element with the value we are looking for as a key:

When the key is less than the middle element,we search in the left half

when the key is more than the middle element,we search in the right half

However,when the key is equal to the middle element,our search target is found and we return the index of the middle element.

Let us update our code to reflect the above steps:

const arr =  [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
      let startIndex = 0;
      let endIndex = arr.length - 1;
      let middleIndex = Math.floor((startIndex + endIndex) / 2 );
      if (elements[middleIndex] === value) {
         return `Target value ${value} was found at index ${middleIndex}`;
         } else if (elements[middleIndex] < value) {
             startIndex = middleIndex + 1;
           } else {
              endIndex = middleIndex - 1;
         }     
 }

To keep going,you enclose the above steps in a loop which will stop when the lower(startIndex) boundary overtakes the upper(endIndex) one.This can easily be achieved by adding a while loop our code as below:

const arr =  [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
      let startIndex = 0;
      let endIndex = arr.length - 1;
      while (startIndex <= endIndex) { 
        let middleIndex = Math.floor((startIndex + endIndex) / 2 );
        if (elements[middleIndex] === value) {
             return `Target value ${value} was found at index ${middleIndex}`;
             } else if (elements[middleIndex] < value) {
                 startIndex = middleIndex + 1;
             } else {
                 endIndex = middleIndex - 1;
            }     
        }
 }

In other words,you can iterate as long as the lower boundary is below or equal to the upper one.Otherwise,there was no match found and the function returns undefined implicitly(lam returning a message informing the user that there was no match found in our array). Our code should now look as below:

'use strict'

const arr =  [0,5,12,23,34,35,46,47,58];

const binarySearch = (elements,value) => {
    let startIndex = 0;
    let endIndex = arr.length - 1;

    while (startIndex <= endIndex) {
        let middleIndex = Math.floor((startIndex + endIndex) / 2);
        if(elements[middleIndex] === value) {
            return `Target value ${value} was found at index ${middleIndex}`;
        }else if(elements[middleIndex] < value) {
            startIndex = middleIndex + 1;
        }else {
            endIndex = middleIndex - 1;
        }
     }
  return `Target value ${value} was not found in [${elements}]`;
}

console.log(`Result of binary search results: ${binarySearch(arr,35)}`);

To ensure your array is always sorted,add the following code:

let sortedArr = arr.sort((a,b) => {
        return a - b;
});

With this addition our code should look as below:

'use strict'

const arr =  [0,5,12,23,34,35,46,47,58];

const binarySearch = (elements,value) => {
    let startIndex = 0;
    let endIndex = arr.length - 1;

    while (startIndex <= endIndex) {
        let middleIndex = Math.floor((startIndex + endIndex) / 2);
        if(elements[middleIndex] === value) {
            return `Target value ${value} was found at index ${middleIndex}`;
        }else if(elements[middleIndex] < value) {
            startIndex = middleIndex + 1;
        }else {
            endIndex = middleIndex - 1;
        }
     }
  return `Target value ${value} was not found in [${elements}]`;
}

let sortedArr = arr.sort((a,b) => {
        return a - b;
});

console.log(`Result of binary search results: ${binarySearch(sortedArr,35)}`);

Sample iteration simulation from our binary search function

Where we can use binary search algorithm

Unlike other search algorithms, binary search can be used beyond just searching. For example, it allows for set membership testing, finding the largest or smallest value, finding the nearest neighbor of the target value, performing range queries, and more.

The Efficiency of Binary Search

The time complexity of the Binary Search is O(log2n), where n is the number of elements in the array. This is far better compared to the Linear Search, which is of time complexity O(n). Like many other search algorithms, Binary Search is an in-place algorithm. That means that it works directly on the original array without making any copies.

We have to keep in mind however, that Binary Search only works on sorted arrays. The sorting step itself, if using an efficient sorting algorithm, has a complexity of O(nlogn). This means that in most cases, if the array is small, or if we need to search it only once, a brute-force (e.g. Linear Search) algorithm might be better.

Given this, Binary Search really shines when we need to make repeated searches on large arrays. As previously mentioned, we needed only 3 comparisons (comparisons being the most intensive tasks of all search algorithms), for my array of 8 elements. However, if we had an array of 10,000,000 elements, we would only need to check 24 elements, i.e. 0.0002%_ of the entire array.

Conclusion

In this article, we have taken a look at Binary Search. It's simple, intuitive and efficient logic and implementation make it a very popular algorithm to demonstrate the divide-and-conquer strategy. Your feedback(s) are highly welcome and shall help me improve on this article or extend my understanding of algorithms.

Data Structures and Algorithms 101

Nemwel Onsando — Mon, 20 Jun 2022 20:03:45 +0000

What is Data Structure?

Is a collection of data values,the relationships among them as well as the operations that can be applied to the data.

In layman language,data structure is something that can be used to store and organize data to be use it in an efficient way when performing data operations.

In its simplistic form:

Data + Structure = Data Structure,
meaning without data(atomic value or collection of facts) and organization(the structure) of the data there is no data structure.

Types of Data Structures

Data Structures can either be:

primitive data structures (also known as built-in data types)- stores data of only one type. Examples are integer,floating point,character,pointer or

non-primitive data structures (also known as derived data types which stores data more than one type. Such type includes array,linked list,queue,tree,graph.

Data Structures enables us to:

Search for elements in the data structure

Traverse or iterate through a data structure in some order

Insert one or more elements into our data structure

Delete elements from our data structure

Update elements to reflect the latest state of our data structure

Sort for reordering of elements in our data structure

Merge for merging elements in our data structure

Advantages of Data Structures

Efficiency - they facilitate efficient storage and retrieval of data for numerous use-cases

Abstraction - each data structure provides clean interfaces in the form of operations exclusive of their abstract data types,making their internal implementation hidden from developers

Composition -fundamental data structures can be combined to build more niche and complex data structures.

Importance of learning data structures

Data Structures are important so as to improve our problem-solving skills and increase efficiency by means of carefully organizing data.

Algorithm

Is a set of rules or step-by-step procedures that are to be executed in a specific order to get the desired output.
or
can also be defined as a finite set of steps carried out in a specific problem-solving operations.Meaning,it is not the complete code,rather it is the logic that can be implemented to solve a particular problem.

Characteristics of algorithm

Unambiguous - it should be clear and simple in nature and lead to meaningful outcome

Input - it should have some input values.

Output - every algorithm should have well-defined outputs

Finiteness - the steps of an algorithm should be countable and it should terminate after the specified number of steps

Effectiveness - each step of an algorithm should be effective and efficient enough to produce results. Effectiveness of an algorithm is evaluated with the help of two parameters:

Time Complexity -which is the amount of time taken by the computer to run an algorithm. This is also called computational complexity of an algorithm. It can either be best-case,average-case or worst-case.We always aim for the best-case for effectiveness.

Space Complexity - which refers to the amount of computational memory needed to solve an instance of the problem.Actually,this is the total space taken by an algorithm with respect to the input size.The lower the space complexity of an algorithm,the faster the algorithm will work.

Language Independent - algorithms should be language independent,meaning the algorithm should work for all programming languages and give same output.

Why we need algorithms

We need algorithms for the following reasons

. Scalability - breaks real-world problems into smaller steps so that it is analyzed easily.
. Performance - algorithm help us break down big problems into smaller modules which makes the problem feasible and provide efficient performance driven solutions.

Factors of an algorithm

When designing and algorithm consider these factors:

Modularity - breaks a big problem into smaller ones.

Correctness - analysis of the problem statement and consequently the algorithm must be correct.It should work correctly for all possible test cases of the problem at hand.A test case here,refers to a specification of inputs,executing conditions,testing procedures and expected results,which we can be developed from the problem statement itself.

Maintainability - it should be designed so as to be easy to maintain and refine it at some point without making major changes.

Functionality - steps of an algorithm should successfully solve a real world problem

User friendly -should be easy to be understood by developers

Simplicity - should be the simplest possible solution to a problem.Simplicity refers to the fact that the algorithm should have the best-case time complexity.It should be simple yet produce desired results in a time-efficient,keeping both time and space complexities in mind.

Extensive - should facilitate re-usability.That is the programmers should be able to reuse it or extend for their own problem statement too.

Example

Problem: Design an algorithm that accept two numbers and print their product

Step 1: START
Step 2: Declare variables a,b and product
Step 3: Read the values of a and b
Step 4: Multiply a and b
Step 5: Store the output of step 4 in product
Step 6: Print product
Step 7: STOP