Author: root

Binary Search is an efficient algorithm for finding a specific value in a sorted array. The basic idea of binary search is to repeatedly narrow down the portion of the array that contains the desired value by splitting the array in half. In this article, we will provide a detailed explanation of the binary search algorithm and solve a problem using it.

Problem Description

The following is a problem that can be solved using binary search:

Problem: Find a specific value in an array using binary search

Given a sorted array nums and an integer target, return the index of target. If target does not exist in the array, return -1. The function assumes that nums is sorted in ascending order.

Examples

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

Principle of the Binary Search Algorithm

The binary search algorithm proceeds with the following steps:

1. Calculate the middle index of the array.
2. Compare the middle value with the desired value (target):
• If the middle value is equal to the target, return the middle index.
• If the middle value is less than the target, search the right half. (from middle index + 1 to the end)
• If the middle value is greater than the target, search the left half. (from the start to middle index – 1)
3. Repeat this process until the exact value is found.

The time complexity of binary search is O(log n), which allows for quick searches in large datasets.

Problem-Solving Process

Now, let’s write the code to solve the above problem. First, we define a function that accepts the array and target.

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

    while (left <= right) {
        const mid = Math.floor((left + right) / 2); // calculate the middle index
        
        if (nums[mid] === target) {
            return mid; // return middle index if found
        } else if (nums[mid] < target) {
            left = mid + 1; // move to the right half
        } else {
            right = mid - 1; // move to the left half
        }
    }

    return -1; // return -1 if the value does not exist
}

Code Explanation

In the above code, the binarySearch function performs binary search on the nums array using the target value as an argument.

1. Sets the search range using the left and right variables. The initial values are the start and end indices of the array, respectively.
2. Uses a while loop to repeat while left is less than or equal to right.
3. Calculates the middle index each iteration and compares the middle value with the target.
4. Adjusts the search range based on conditions and ultimately returns -1 if the value is not found.

Example Execution

Below is an example execution of the binary search function:

const nums = [-1,0,3,5,9,12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Result Analysis

Through the above examples, we can see that the function outputs the correct index. binarySearch(nums, 9) returns 4, and binarySearch(nums, 2) returns -1.

Conclusion

Binary search is a very efficient search algorithm that allows for a quick search of desired values in sorted data. I hope this lecture has helped you understand the principles and implementation methods of binary search. Since it is also a common algorithm that appears in coding tests, it is essential to familiarize yourself with it and practice.

Welcome to the blog! Today, we will learn both the theory and practical implementation by solving problems using DFS (Depth-First Search) and BFS (Breadth-First Search) algorithms.

Problem Description

We will tackle the problem of finding the shortest path to a specific node in a given undirected graph. The graph is provided in the form of an adjacency list, and the shortest path can be found using BFS. DFS can be used to verify the existence of a path rather than finding the shortest path.

Problem

Input:
- n: number of vertices (1 ≤ n ≤ 10^4)
- edges: list of edges (undirected)
- start: starting vertex
- end: ending vertex

Output:
- List of edges that form the shortest path from start to end
            

Example

Input: n = 5, edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]], start = 1, end = 5

Output: [1, 2, 4, 5] or [1, 3, 4, 5]

Theory

DFS (Depth-First Search)

DFS is a method that starts from a node in the graph and explores as far as possible along each branch before backtracking. This algorithm can be implemented recursively or using a stack. The advantage of DFS is its low memory usage, making it useful when deep node exploration is needed.

BFS (Breadth-First Search)

BFS explores all neighboring nodes at the present depth prior to moving on to nodes at the next depth level. It is implemented using a queue and is particularly suitable for finding the shortest path. BFS is very useful in finding the shortest path, ensuring that it exists if a shortest path is available.

Solution

Step 1: Build the Graph

First, let’s build the graph using an adjacency list.

function buildGraph(n, edges) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u); // Since it's an undirected graph, add both ways
    }
    return graph;
}

const n = 5;
const edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]];
const graph = buildGraph(n, edges);
console.log(graph);
            

Step 2: Implement BFS

Now, let’s find the shortest path from the starting vertex to the ending vertex using BFS.

function bfs(graph, start, end) {
    const queue = [[start]];
    const visited = new Set([start]);

    while (queue.length > 0) {
        const path = queue.shift();
        const node = path[path.length - 1];

        if (node === end) {
            return path; // Return the shortest path found
        }

        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([...path, neighbor]); // Add neighboring node to current path
            }
        }
    }
    return []; // Return empty array if no path found
}

const start = 1,
      end = 5;

const result = bfs(graph, start, end);
console.log(result);
            

Step 3: Implement DFS

Now, let’s use DFS to check the existence of a path and how to find that path.

function dfs(graph, start, end, visited = new Set(), path = []) {
    visited.add(start);
    path.push(start);
    
    if (start === end) {
        return path; // Return when the path is found
    }

    for (const neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            const resultPath = dfs(graph, neighbor, end, visited, [...path]);
            if (resultPath.length > 0) {
                return resultPath; // Return when a path is discovered
            }
        }
    }
    return []; // Return empty array if no path found
}

const dfsResult = dfs(graph, start, end);
console.log(dfsResult);
            

Hello, everyone! In this post, we will explore the ‘Least Common Ancestor (LCA)’ problem, which frequently appears in JavaScript coding tests. This problem is a very important concept when dealing with tree structures. We will implement an algorithm to find the least common ancestor and take a detailed look at the process.

Problem Description

This is the problem of finding the least common ancestor of two nodes in a given binary tree. The tree follows these rules:

• Each node can have at most two children.
• The given two nodes always exist in the tree.

Input

• Address of the root node of the tree (root)
• Address of the first node (node1)
• Address of the second node (node2)

Output

Print the node value of the least common ancestor of the two nodes.

Example

Input:
          3
         / \
        5   1
       / \ / \
      6  2 0  8
        / \
       7   4
       
       node1 = 5, node2 = 1
       
Output:
3

Solution

There can be several approaches to solve this problem. However, the most common approach is to use DFS (Depth First Search). This method allows us to find the least common ancestor by visiting each node. Let’s examine this process step by step.

Step 1: Define the Tree Structure

First, we need to create a class defining the tree. In JavaScript, a tree node can generally be defined as follows:

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null; // left child
        this.right = null; // right child
    }
}

Step 2: Create the Tree

Let’s write sample code to create the tree. The following code creates a tree like the one in the example above:

const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

Step 3: Implement the DFS Algorithm

Now it’s time to implement the DFS algorithm. The process for finding the least common ancestor follows these steps:

1. If the current node is null, return null.
2. If the current node is equal to node1 or node2, return the current node.
3. Recursively call the left and right children to obtain the results.
4. If both left and right child node results are not null, the current node is the least common ancestor.
5. If only one of the left or right children is not null, return the non-null child.

function lowestCommonAncestor(root, node1, node2) {
    if (root === null) return null;
    if (root.value === node1.value || root.value === node2.value) return root;

    const left = lowestCommonAncestor(root.left, node1, node2);
    const right = lowestCommonAncestor(root.right, node1, node2);

    if (left && right) return root;
    return left ? left : right;
}

Step 4: Output the Result

Now that the least common ancestor algorithm is complete, let’s test it:

const lca = lowestCommonAncestor(root, root.left, root.right); // node1: 5, node2: 1
console.log(lca.value); // 3

Summary and Conclusion

In this post, we covered the Least Common Ancestor (LCA) problem. We defined the tree structure, implemented an algorithm using DFS, and verified the results through examples. The key point is that this algorithm visits each node through recursive calls, structurally setting conditions to find the least common ancestor.

Such problems have various forms, so it is important to practice solving different types of problems. We will continue to introduce various algorithms that will help you prepare for JavaScript coding tests, so please stay tuned!

References

• GeeksforGeeks – Lowest Common Ancestor in a Binary Tree
• ProgramCreek – LeetCode: Lowest Common Ancestor of a Binary Tree

I hope this helps you prepare for your coding tests. Thank you!

Problem Description

You are in charge of delivering gifts to several friends. To deliver gifts to each friend, you need their unique ID. When given the ID of all friends and the ID of gifts, you need to determine whether the gifts can be delivered.

Problem Definition

Each friend is assumed to have the following information:

• Friend’s ID
• ID of the gift they want
• Signal (whether this friend can receive the gift or not)

The input array contains information about several friends. Based on each friend’s ID and the ID of the gift they want, write a function to determine whether the gifts can be delivered accurately.

Input Format

    [
        { friendId: 1, giftId: 101, signal: true },
        { friendId: 2, giftId: 102, signal: false },
        { friendId: 3, giftId: 101, signal: true }
    ]
    

Output Format

    [
        { friendId: 1, giftId: 101, canReceive: true },
        { friendId: 2, giftId: 102, canReceive: false },
        { friendId: 3, giftId: 101, canReceive: true }
    ]
    

Solution Method

To solve this problem, you need to iterate through the array containing each friend’s information and determine if they can receive the gift. Basically, if the friend’s ID and the gift’s ID match, it’s assumed that they can receive the gift. However, if the friend’s signal value is false, they cannot receive the gift, so this needs to be taken into account.

Algorithm Explanation

    function canGiftsBeReceived(friends) {
        return friends.map(friend => {
            const canReceive = (friend.signal === true && friend.friendId === friend.giftId);
            return { ...friend, canReceive: canReceive };
        });
    }
    

The code above takes the given friends’ information and determines whether each friend can receive the gift, returning a new array.

Detailed Steps

1. Function Definition: Define a function named canGiftsBeReceived that takes a parameter friends. This parameter is an array containing friends’ information.
2. Iterate Through Array: Use the map method to iterate through the given friends array. Use a local variable named friend for each friend.
3. Condition Check: For each friend, check if signal is true and if friendId matches giftId, saving the result in the canReceive value.
4. Create Result Object: Create a new object based on each friend’s information. This object includes the existing friend information and the canReceive value.
5. Return Result: Finally, return the transformed array.

Example Code

    const friends = [
        { friendId: 1, giftId: 101, signal: true },
        { friendId: 2, giftId: 102, signal: false },
        { friendId: 3, giftId: 101, signal: true }
    ];

    const result = canGiftsBeReceived(friends);
    console.log(result);
    

Result

    [
        { friendId: 1, giftId: 101, signal: true, canReceive: true },
        { friendId: 2, giftId: 102, signal: false, canReceive: false },
        { friendId: 3, giftId: 101, signal: true, canReceive: true }
    ]
    

The results above clearly show whether each friend can receive the gift. This method ensures safe delivery of gifts.

Conclusion

In this lecture, we explored a problem-solving method using basic arrays and objects. To solve algorithmic problems, it’s important to systematically analyze the problem and apply the appropriate algorithm. I hope this helps you tackle various problems using JavaScript.