JavaScript: 2 Ways to Find the Nearest Value in an Array

Introduction

When you work with arrays in JavaScript, a common task is to locate the element nearest to a given value. Whether for numeric arrays or more complex data structures, JavaScript provides different approaches to achieve this. Various solutions offer a trade-off between ease of implementation and performance. This tutorial introduces the different ways to find the nearest value in an array using JavaScript.

Solution 1: Linear Search

Performing a linear search is a straightforward approach to find the nearest value by iterating through each element in the array and comparing it to the target value.

1. Initialize the nearest value and the smallest difference.
2. Loop through each element in the array.
3. Calculate the absolute difference between the target value and each element.
4. If the calculated difference is smaller than the smallest difference, update the nearest value and the smallest difference.
5. Repeat the process until the end of the array.
6. Return the nearest value.

Example:

const findNearest = (arr, target) => {
  let nearest = arr[0];
  let smallestDifference = Math.abs(target - nearest);
  for (let i = 1; i < arr.length; i++) {
    const difference = Math.abs(target - arr[i]);
    if (difference < smallestDifference) {
      nearest = arr[i];
      smallestDifference = difference;
    }
  }
  return nearest;
};

console.log(findNearest([5, 20, 12, 16, 22], 15)); // Output: 16

Notes: The linear search solution has a O(n) complexity where n is the size of the array. This approach is simple but not optimized for large datasets. Performing well on smaller arrays but may become inefficient for large arrays.

Solution 2: Sort and Binary Search

By sorting the array first, you can apply a binary search technique to find the element nearest to a given value, significantly reducing the search time.

1. Sort the array in ascending order.
2. Implement a binary search to locate the nearest value.
3. If the exact match is found, return it.
4. Use two pointers to find the closest values when there’s no exact match.
5. Return the nearest value based on which pointer indicates the smaller difference to the target.

Example:

const findNearestUsingBinarySearch = (arr, target) => {
  arr.sort((a, b) => a - b);
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] === target) return arr[mid];
    if (arr[mid] < target) start = mid + 1;
    else end = mid - 1;
  }
  const closest = (target - arr[end] <= arr[start] - target) ? arr[end] : arr[start];
  return closest;
};

console.log(findNearestUsingBinarySearch([5, 20, 12, 16, 22], 15)); // Output: 16

Notes: Sorting the array first introduces an additional O(n log n) complexity. The binary search itself has a O(log n) complexity, thus it is more efficient on sorted datasets. Sorting might not be feasible if the order in the original array must be preserved or if sorting introduces a significant overhead.

Conclusion

Identifying the nearest value in an array can be achieved through various methods in JavaScript, each with its own characteristics. Linear search is easy to understand and implement but does not perform well with large datasets. On the other hand, sorting the array before employing a binary search optimizes the search operation, particularly compelling for large, sortable arrays. Developers should choose the approach that best fits their circumstance, considering factors such as array size, need to maintain the original order, and performance implications.