JavaScript Coding Test Course, Utilizing Time Complexity

Problem Description

This problem is about finding the number closest to a given num value in the provided array arr. If there are multiple closest numbers, the one closer to num with a lower value takes precedence.

Input

• An integer array arr (-10⁶ ≤ arr[i] ≤ 10⁶, 1 ≤ arr.length ≤ 10⁵)
• An integer num (-10⁶ ≤ num ≤ 10⁶)

Output

Return the closest number.

Examples

Example 1:
Input: arr = [1, 2, 3, 4, 5], num = 3
Output: 3

Example 2:
Input: arr = [1, 2, 4, 5], num = 3
Output: 2

Example 3:
Input: arr = [5, 10, 15], num = 12
Output: 10

Solution Process

To solve this problem, we follow these steps.

Step 1: Understand the Problem

First, since the task is to find the number closest to num, the key is to calculate the absolute differences between each element and num and find the smallest value. If there are multiple numbers with the same difference, the smaller value should be returned.

Step 2: Choose an Approach

The simplest method is to iterate through the array and calculate the absolute differences for each element. However, this has a time complexity of O(n), so we need to consider a faster algorithm.

Step 3: Utilize Binary Search through Sorting

By sorting the input array, we can efficiently find the number closest to num using binary search. To find the index of a specific value num in the sorted array, we will use Array.prototype.sort() and then implement a binarySearch() function.

Step 4: Implement the Code

Below is the JavaScript code based on the above explanation.

function findClosest(arr, num) {
    // Sort the array
    arr.sort((a, b) => a - b);
    
    let left = 0;
    let right = arr.length - 1;
    let closest = arr[0];

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        // Compare absolute differences
        if (Math.abs(arr[mid] - num) < Math.abs(closest - num) ||
            (Math.abs(arr[mid] - num) === Math.abs(closest - num) && arr[mid] < closest)) {
            closest = arr[mid];
        }
        
        // Determine the direction of binary search
        if (arr[mid] < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return closest;
}

// Example Tests
console.log(findClosest([1, 2, 3, 4, 5], 3)); // 3
console.log(findClosest([1, 2, 4, 5], 3));    // 2
console.log(findClosest([5, 10, 15], 12));      // 10

Step 5: Analyze Time Complexity

The above code first sorts the array, which has a time complexity of O(n log n), and then the searching process using binary search requires O(log n) time. Therefore, the overall time complexity can be evaluated as O(n log n).

Conclusion

This problem has taught us the importance of choosing an efficient algorithm considering time complexity. It is necessary to try various approaches for the given problem and select the appropriate algorithm based on the results. I hope you apply these principles well in future coding tests!