在 JavaScript 中搜索已排序的二维数组

Z时代
2024-01-10
分类：综合

我们需要编写一个 JavaScript 函数，它接受一个数字数组作为第一个参数，一个数字作为第二个参数。子数组包含按递增顺序排序的数字，并且前一个子数组的任何元素都不大于后继子数组的任何元素。

该函数应该使用二分搜索算法来搜索作为排序数组中的第二个参数提供的元素。

如果元素存在，函数应该返回真，否则返回假。

例如 -

如果输入数组是 -

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

那么输出应该是 -

const output = 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 arr = getArr();
   if (!arr) { return false; }
      return binarySearch(arr, target) !== null;
   function getArr() {
      for (let i = 0; i < h; i++) {
         let arr = array[i];
         if (arr[0] <= target && target <= arr[arr.length - 1]) {
            return arr;
         }
      }
      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 if (arr[mid] > t) {
            right = mid - 1;
         }
      }
      return null;
   }
};
console.log(search2D(arr, num))