การค้นหาแบบทวิภาคในอาร์เรย์ 2 มิติที่จัดเรียงแล้วใน JavaScript

บทความนี้สาธิตการค้นหา target ใน matrix 2D ที่แต่ละ row จัดเรียงเพิ่ม และ row ถัดไปมีค่าทุกตัวมากกว่า row ก่อนหน้า

ตัวอย่าง

arr = [[2,6,9,11], [13,16,18,19,21], [24,26,28,31]]
target = 21 -> true

ตัวอย่างโค้ด

const arr = [
  [2, 6, 9, 11],
  [13, 16, 18, 19, 21],
  [24, 26, 28, 31]
];
const num = 21;

const search2D = (array = [], target) => {
  const h = array.length;
  const w = h > 0 ? array[0].length : 0;
  if (h === 0 || w === 0) { return false; }
  const rowArr = getArr();
  if (!rowArr) { return false; }
  return binarySearch(rowArr, target) !== null;

  function getArr() {
    for (let i = 0; i < h; i++) {
      let row = array[i];
      if (row[0] <= target && target <= row[row.length - 1]) {
        return row;
      }
    }
    return null;
  }

  function binarySearch(arr, t) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
      if (arr[left] === t) return left;
      if (arr[right] === t) return right;
      let mid = Math.floor((left + right) / 2);
      if (arr[mid] === t) return mid;
      if (arr[mid] < t) left = mid + 1;
      else right = mid - 1;
    }
    return null;
  }
};

console.log(search2D(arr, num));

ผลลัพธ์

true

คำอธิบาย

หา row ที่ target อาจอยู่ (row[0] <= target <= row[last]) แล้ว binary search ใน row นั้น

Time: O(log m + log n) โดย m = rows, n = cols

หมายเหตุ: โค้ดสมมติทุก row มีความยาวเท่ากัน แต่ตัวอย่าง row 2 มี 5 elements, row 1,3 มี 4 elements โค้ดยังทำงานได้เพราะใช้ row.length จริง