Skip to main content

Binary Search in JavaScript

It's like finding a house number on a long street — instead of starting from one end, you begin in the middle, and, based on whether the house number is higher or lower, you search the right or left half of the list.

We'll learn to:

  1. Understand Binary Search.

  2. Implement Binary Search using recursion and iteration in JavaScript.

  3. Analyse the time complexity of Binary Search.


Unveiling Binary Search

Binary Search follows a divide-and-conquer strategy. It starts in the middle of a sorted list. If the middle value is the desired one, great! If not, it uses the sorted nature of the list to eliminate half of it. The side to eliminate is selected based on whether the target is smaller or larger than the middle value.

Implementing Binary Search Using Recursion in JavaScript

Let's implement Binary Search in JavaScript using recursion. Here's the code, accompanied by detailed comments:

This function calls itself recursively, gradually shrinking the search area until it finds the target.

Implementing Binary Search Using Iteration in JavaScript

Here, we create a Binary Search using a while loop in JavaScript:

In this version, the function does not call itself. Instead, it uses a while loop to achieve the same goal.

Analysing Complexity of Binary Search

Binary Search reduces the input size by half on every step, hence it takes log(n) steps to find a target in an array of size n. Thus, the time complexity of Binary Search is O(log n). Both recursive and iterative approaches share the same time complexity — O(log n). Their choice usually comes down to specific problems, constraints, and personal preferences.
Labels:

Comments

Post a Comment

Popular posts from this blog

JavaScript Maps

Dive Into JavaScript Maps A Map stores data as key-value pairs. We'll recall how to create Maps, implement them, and delve into the details of their memory management. Understanding JavaScript Maps Maps are versatile data structures in JavaScript. They store key-value pairs and accept any data type as a key — even objects and functions! Here is how we create an empty Map: let myMap = new Map(); // creates an empty Map Here, myMap is a new JavaScript Map, eagerly awaiting to store your keys and values. Meander Through Map Methods Maps provide some essential built-in methods: set(key, value): Stores a key-value pair. get(key): Retrieves the value of a key. has(key): Checks if a key exists and returns true or false. delete(key): Erases a key-value pair. size: Returns the count of key-value pairs. To gain a better understanding, let's apply these methods: let myMap = new Map(); // Add pairs with set myMap.set('apples', 10); // Adds a new pair myMap.set('bananas', 6...
Post a Comment
Read more

How to work with Set in JavaScript

Understanding JavaScript Sets Set in JavaScript is an unordered collection of unique values. We can examine the size of the set using .size method. Notice that the set is unordered, and we can't guarantee that elements will be shown in the order we added them. Sets work similarly to JavaScript objects but are designed for uniqueness. They use hashing, a way to convert a given pearl into a unique code, which facilitates rapid storage and retrieval. When checking if an item is in a Set, JavaScript computes its hash code to locate it, much like a map leading to a treasure. Sets have numerous practical uses in database management, data analysis , and more . Problem 1: Check if Two Sets are Disjoint Let's begin by considering the function, areDisjoint which takes two arrays and determines if they are disjoint, meaning they have no elements in common. This is crucial when analysing datasets for overlapping values, similar to ensuring that two puzzle pieces from different puzzles d...
Post a Comment
Read more

The Synergy Between DevOps and Agile Methodologies

When it comes to modern software development practices, two methodologies have gained significant traction in recent years: DevOps and Agile. While they are distinct in their approaches, DevOps and Agile share common goals of improving collaboration, efficiency, and quality in software development processes. Understanding DevOps DevOps  is a set of practices that combines software development (Dev) and IT operations (Ops) to shorten the systems development life cycle and provide continuous delivery of high-quality software. It emphasizes collaboration, automation, and monitoring throughout the software delivery process. Key principles of DevOps include: Automation of processes Continuous integration and delivery Monitoring and feedback loops Collaboration between teams Exploring Agile Methodologies Agile  is an iterative approach to software development that focuses on delivering value to customers through incremental and iterative development. Agile methodologies promote adap...
Post a Comment
Read more