Software Studio Pro

GOTO

Introduction Linear Search Binary Search Hash Tables Map & Set Binary Search Tree (BST)

BLOG ON

Search a list in JavaScript

UPDATED ON - 5th September, 2024

PUBLISHED BY

Aditya Prem Sharma

Frontend Developer

Introduction Linear Search Binary Search Hash Tables Map & Set Binary Search Tree (BST)

Introduction

Best and fastest algorithm for searching in a list (array) in JavaScript depends on various factors such as the size of the list, the nature of the data, and the specific requirements of your application. The choice of algorithm depends on factors such as the size of your data, how often you need to perform searches, whether the data is sorted, and memory constraints. Always consider these factors before deciding on an algorithm.

Here are a few common options:

Linear Search: This is the simplest search algorithm where you iterate over each element in the list until you find the desired element. It's straightforward but not the most efficient, especially for large lists. However, it's suitable for unsorted lists.

Binary Search: This algorithm works only on sorted lists. It's much faster than linear search for large lists because it eliminates half of the remaining elements at each step. In JavaScript, arrays need to be sorted before applying binary search. JavaScript's built-in Array.prototype.indexOf() and Array.prototype.includes() methods use optimized algorithms which are likely more efficient than a naive linear search.

Hash Tables (or JavaScript Objects): If you're looking for exact matches and you have control over the structure of your data, using a hash table (implemented in JavaScript as an object) can provide constant time complexity O(1) for search operations in the average case. However, this assumes that there are no hash collisions and that the hashing function is well-distributed.

Map and Set: JavaScript also provides Map and Set data structures. If you're dealing with unique values, using a Set could be efficient for searching. If you need key-value pairs, Map might be more suitable.

Tree-based Structures (e.g., Binary Search Trees): These data structures can offer efficient searching as well, especially for larger datasets. However, implementing these structures from scratch might require more effort.

Optimized Libraries and Functions: JavaScript libraries and frameworks often provide optimized search algorithms for specific use cases. For example, if you're dealing with a large dataset and need powerful search capabilities, you might consider using libraries like lodash or implementing search algorithms from libraries like lodash or underscore.

Linear Search

Linear search, also known as sequential search, is one of the simplest searching algorithms. It works by sequentially checking each element in a list or array until the desired element is found or the end of the list is reached.

JS CODE

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {

            return i; // Return the index if found
        }
    }
    return -1; // Return -1 if not found
}

// Example usage:
const myArray = [3, 1, 4, 2, 5];
const targetElement = 4;
console.log(linearSearch(myArray, targetElement)); // Output: 2 (index of targetElement)

Here's how the linear search algorithm works:

1. Start at the beginning: The algorithm starts at the first element of the list.

2. Compare: It compares the target element with the current element being examined.

3. Match found?: If the current element matches the target element, the search is successful, and the algorithm returns the index of the current element.

4. Move to the next element: If the current element does not match the target element, the algorithm moves to the next element in the list.

5. Repeat: Steps 2-4 are repeated until either the target element is found or the end of the list is reached.

6. End of list reached: If the end of the list is reached without finding the target element, the algorithm concludes that the element is not present in the list, and it returns a special value (often -1) to indicate that the search was unsuccessful.

Summary:

Linear search is straightforward and easy to implement, making it suitable for small lists or situations where the list is not sorted. However, it's not the most efficient algorithm for large lists because it has a time complexity of O(n), where n is the number of elements in the list. This means that in the worst-case scenario, the algorithm may need to examine every element in the list before finding the target element or concluding that it's not present.

Binary Search

Binary search is a more efficient searching algorithm compared to linear search, especially for sorted lists. It follows a divide-and-conquer approach to quickly locate a target element within a sorted list.

JS CODE

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid; // Return the index if found
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Return -1 if not found
}

// Example usage:
const sortedArray = [1, 2, 3, 4, 5];
const targetElement = 4;
console.log(binarySearch(sortedArray, targetElement)); // Output: 3 (index of targetElement)

Here's how the binary search algorithm works:

1. Start at the middle: The algorithm starts by examining the middle element of the sorted list.

2. Compare with the target: It compares the middle element with the target element.

3. Match found?: If the middle element matches the target element, the search is successful, and the algorithm returns the index of the middle element.

4. Narrow down the search range: If the target element is less than the middle element, the algorithm knows that the target (if present) must be in the left half of the list. Similarly, if the target element is greater than the middle element, the algorithm narrows down the search to the right half of the list.

5. Repeat: Steps 2-4 are repeated on the narrowed-down range of the list until either the target element is found or the search range becomes empty.

6. Target not found: If the search range becomes empty without finding the target element, the algorithm concludes that the element is not present in the list, and it returns a special value (often -1) to indicate that the search was unsuccessful.

Summary:

Binary search has a time complexity of O(log n), where n is the number of elements in the list. This means that the algorithm efficiently reduces the search range by half with each comparison, making it particularly suitable for large sorted lists.

Hash Tables

Hash tables, also known as hash maps, are a type of data structure that stores key-value pairs. They provide efficient insertion, deletion, and retrieval of elements, making them ideal for situations where fast access to data is required.

JS CODE

// Using JavaScript object as a hash table
const hashTable = {};


function addToHashTable(key, value) {
    hashTable[key] = value;
}

function searchInHashTable(key) {
    return hashTable[key];
}

// Example usage:
addToHashTable("apple", 5);
addToHashTable("banana", 10);
console.log(searchInHashTable("apple")); // Output: 5
console.log(searchInHashTable("banana")); // Output: 10
console.log(searchInHashTable("orange")); // Output: undefined

Here's how hash tables work:

1. Hashing function: Hash tables use a hashing function to convert keys into indices (hash codes) of an array where the corresponding values will be stored. The hashing function should ideally distribute the keys uniformly across the array to minimize collisions (when two different keys produce the same hash code).

2. Array storage: Hash tables typically use an array to store the key-value pairs. Each slot (or bucket) in the array can hold multiple key-value pairs, either as a linked list or an array, depending on the implementation.

3. Insertion: When inserting a key-value pair into a hash table, the hashing function is applied to the key to determine the index where the value will be stored in the array. If the slot at that index is empty, the key-value pair is inserted directly. If the slot is already occupied, collision resolution strategies are employed to handle collisions. Common strategies include chaining (using linked lists or arrays to store multiple key-value pairs at the same index) and open addressing (finding an alternative empty slot within the array).

4. Retrieval: When retrieving a value associated with a key, the hashing function is again applied to the key to determine the index where the value is stored. If the slot at that index contains the desired key-value pair, the value is returned. If not, collision resolution strategies are used to locate the correct key-value pair.

5. Deletion: Deleting a key-value pair from a hash table involves first locating the slot containing the key-value pair and then removing it. If the slot contains multiple key-value pairs (due to collisions), the appropriate collision resolution strategy is used to find and remove the specific key-value pair.

Summary:

Hash tables provide constant-time average-case complexity O(1) for insertion, deletion, and retrieval operations, assuming a good hashing function and uniform distribution of keys. However, in the worst case, when collisions are frequent, the time complexity can degrade to O(n), where n is the number of key-value pairs in the hash table.

Map & Set

Maps and Sets are data structures available in JavaScript that provide efficient storage and retrieval of data.

Map: A Map is a collection of key-value pairs where each unique key maps to a specific value. Unlike objects in JavaScript, keys in a Map can be of any data type (including objects and functions), and the order of insertion is preserved.

Set: A Set is a collection of unique values, where each value can occur only once. Sets can store any type of value, including primitive types and objects.

JS CODE

// Using Map
const map = new Map();
map.set("apple", 5);

map.set("banana", 10);

console.log(map.get("apple")); // Output: 5
console.log(map.get("banana")); // Output: 10
console.log(map.get("orange")); // Output: undefined

// Using Set
const set = new Set([1, 2, 3, 4, 5]);

console.log(set.has(3)); // Output: true
console.log(set.has(6)); // Output: false

Here's how Maps work:

1. Insertion: You can add key-value pairs to a Map using the set() method. If the key already exists, its value is updated; otherwise, a new key-value pair is added.

2. Retrieval: You can retrieve the value associated with a key using the get() method. If the key exists, the method returns the corresponding value; otherwise, it returns undefined.

3. Deletion: You can remove a key-value pair from a Map using the delete() method. If the key exists, the method removes the key-value pair and returns true; otherwise, it returns false.

4. Iteration: You can iterate over the key-value pairs in a Map using methods like forEach(), keys(), values(), or entries().

Here's how Sets work:

1. Insertion: You can add values to a Set using the add() method. If the value already exists in the Set, it is not added again.

2. Retrieval: You can check if a value exists in a Set using the has() method. If the value exists, the method returns true; otherwise, it returns false.

3. Deletion: You can remove a value from a Set using the delete() method. If the value exists, the method removes it from the Set and returns true; otherwise, it returns false.

4. Iteration: You can iterate over the values in a Set using methods like forEach().

Summmary:

Maps provide constant-time complexity O(1) for insertion, retrieval, and deletion operations, making them efficient for storing and accessing data.

Sets provide constant-time complexity O(1) for insertion, retrieval, and deletion operations, making them efficient for storing unique values and performing set operations such as union, intersection, and difference.

Binary Search Tree (BST)

A Binary Search Tree (BST) is a hierarchical data structure consisting of nodes, where each node has a value and two child nodes (left and right). The key property of a BST is that for every node:

1. All values in the left subtree are less than the node's value.

2. All values in the right subtree are greater than the node's value.

JS CODE

class Node {
    constructor(data) {
        this.data = data;

        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    insert(data) {
        const newNode = new Node(data);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    insertNode(node, newNode) {
        if (newNode.data < node.data) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    search(data) {
        return this.searchNode(this.root, data);
    }

    searchNode(node, data) {
        if (node === null) {
            return null;
        }

        if (data < node.data) {
            return this.searchNode(node.left, data);
        } else if (data > node.data) {
            return this.searchNode(node.right, data);
        } else {
            return node; // Return the node if found
        }
    }
}

// Example usage:
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(18);

console.log(bst.search(7)); // Output: Node { data: 7, left: null, right: null }
console.log(bst.search(20)); // Output: null (not found)

Here's how Binary Search Trees work:

1. Insertion: When inserting a new node into a BST, it starts at the root node. If the tree is empty, the new node becomes the root. Otherwise, the algorithm compares the value of the new node with the value of the current node. If the new node's value is less than the current node's value, it goes to the left subtree; otherwise, it goes to the right subtree. This process continues recursively until an appropriate empty spot is found, and the new node is inserted as a leaf.

2. Search: Searching in a BST is efficient due to its structure. Starting from the root, the algorithm compares the target value with the value of the current node. If they match, the search is successful. If the target value is less than the current node's value, the algorithm continues searching in the left subtree; otherwise, it searches in the right subtree. This process repeats until the target value is found or until a leaf node is reached (indicating that the value is not in the tree).

3. Deletion: Deleting a node from a BST involves three cases:

- If the node to be deleted is a leaf node, it can be removed directly.

- If the node to be deleted has only one child, the child can take its place.

- If the node to be deleted has two children, it can be replaced by its inorder successor (or predecessor), which is the minimum (or maximum) value in its right (or left) subtree.

4. Traversal: There are several ways to traverse a BST:

- Inorder traversal: Visit the left subtree, then the current node, and finally the right subtree. This yields nodes in sorted order.

- Preorder traversal: Visit the current node, then the left subtree, and finally the right subtree.

- Postorder traversal: Visit the left subtree, then the right subtree, and finally the current node.

Sumary:

Binary Search Trees provide average-case time complexity of O(log n) for insertion, deletion, and search operations, where n is the number of nodes in the tree. However, in the worst case (when the tree is unbalanced), the time complexity can degrade to O(n), making it less efficient. Balancing techniques such as AVL trees and Red-Black trees are used to maintain a balanced BST and ensure efficient operations.

Ready to bring your business idea to life? Contact us today and let's build something amazing together!

Contant Us

Search a list in JavaScript

Aditya Prem Sharma

Table of Contents

Introduction

Here are a few common options:

Linear Search

JS CODE

Here's how the linear search algorithm works:

Summary:

Binary Search

JS CODE

Here's how the binary search algorithm works:

Summary:

Hash Tables

JS CODE

Here's how hash tables work:

Summary:

Map & Set

JS CODE

Here's how Maps work:

Here's how Sets work:

Summmary:

Binary Search Tree (BST)

JS CODE

Here's how Binary Search Trees work:

Sumary:

READ MORE BLOGS

QUICK LINKS

Our Apps

COMPANY

Log In

For Creators and Admin

Search a list in JavaScript

Aditya Prem Sharma

Table of Contents

Introduction

Here are a few common options:

Linear Search

JS CODE

Here's how the linear search algorithm works:

Summary:

Binary Search

JS CODE

Here's how the binary search algorithm works:

Summary:

Hash Tables

JS CODE

Here's how hash tables work:

Summary:

Map & Set

JS CODE

Here's how Maps work:

Here's how Sets work:

Summmary:

Binary Search Tree (BST)

JS CODE

Here's how Binary Search Trees work:

Sumary:

READ MORE BLOGS

QUICK LINKS

Our Apps

COMPANY