Tìm chỉ số phần tử gần giá trị cho trước nhất trong mảng JavaScript

Mô tả bài toán

Cho mảng số đã sắp xếp và giá trị n, tìm chỉ số phần tử có khoảng cách tuyệt đối nhỏ nhất đến n.

Ví dụ minh họa

const arr = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];

const closestIndex = (num, arr) => {
  let curr = arr[0], diff = Math.abs(num - curr);
  let index = 0;
  for (let val = 0; val < arr.length; val++) {
    let newdiff = Math.abs(num - arr[val]);
    if (newdiff < diff) {
      diff = newdiff;
      curr = arr[val];
      index = val;
    }
  }
  return index;
};

console.log(closestIndex(150, arr));

Kết quả

4

Giải thích

arr[4] = 162, |150-162| = 12. arr[3] = 122, |150-122| = 28. Vì mảng đã sắp xếp, có thể dùng binary search O(log n).

Binary search tối ưu

const closestIndex = (num, arr) => {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;
    if (arr[m] === num) return m;
    if (arr[m] < num) l = m + 1;
    else r = m - 1;
  }
  // l là vị trí chèn, so sánh l và l-1
  if (l === 0) return 0;
  if (l === arr.length) return arr.length - 1;
  return (num - arr[l-1] <= arr[l] - num) ? l-1 : l;
};