Chúng ta cần viết một hàm JavaScript nhận vào một mảng các mảng số làm đối số đầu tiên và một số làm đối số thứ hai. Các mảng con chứa số được sắp xếp theo thứ tự tăng dần và không có phần tử của mảng con trước lớn hơn bất kỳ phần tử nào của mảng con sau.
Hàm nên sử dụng thuật toán tìm kiếm nhị phân để tìm kiếm phần tử được cung cấp làm đối số thứ hai trong mảng các mảng đã sắp xếp.
Nếu phần tử tồn tại hàm trả về true, ngược lại false.
Ví dụ:
Nếu mảng đầu vào là:
const arr = [ [2, 6, 9, 11], [13, 16, 18, 19, 21], [24, 26, 28, 31] ]; const num = 21;
Thì đầu ra nên là:
const output = true;
Ví dụ
Dưới đây là mã nguồn:
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))Kết quả
Đầu ra trên console:
true
Giải thích: Ma trận có tính chất: mỗi hàng sort tăng, hàng sau lớn hơn hàng trước. Cách 1: Tìm hàng chứa target (O(log rows) binary search hoặc O(rows) linear), rồi binary search trong hàng (O(log cols)). Cách 2: Coi như mảng 1D phẳng, binary search O(log(m*n)). Code dùng cách 1.