74.搜索二维矩阵.md

74.搜索二维矩阵

/*
 * @lc app=leetcode.cn id=74 lang=typescript
 *
 * [74] 搜索二维矩阵
 */

// @lc code=start
function searchMatrix(matrix: number[][], target: number): boolean {}
// @lc code=end

解法 1: 两次二分查找

function searchMatrix(matrix: number[][], target: number): boolean {
  for (const arr of matrix) {
    if (target < arr[0]) break

    if (target <= arr[arr.length - 1]) {
      let left = 0,
        right = arr.length - 1
      while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (arr[mid] === target) return true

        if (arr[mid] < target) {
          left = mid + 1
        } else {
          right = mid - 1
        }
      }

      break
    }
  }
  return false
}

解法 2: 两次二分查找

function searchMatrix(matrix: number[][], target: number): boolean {
  const row = binarySearch(
    matrix,
    mid => matrix[mid][0] > target,
    mid => matrix[mid][matrix[mid].length - 1] < target,
    mid => matrix[mid],
    () => [],
  )
  if (row.length === 0) return false
  return binarySearch(
    row,
    mid => row[mid] > target,
    mid => row[mid] < target,
    () => true,
    () => false,
  )
}

/**
 *
 * @param arr 要进行二分查找的数组
 * @param compare1 比较函数,如果返回 true,则会将 right 左移
 * @param compare2 比较函数,如果返回 true,则会将 left 右移
 * @param succeed 当中值就是要查找的目标时,执行的函数,函数值作为搜索的结果返回
 * @param failure 当迭代结束后,执行的函数,函数值作为搜索的结果返回
 * @returns
 */
function binarySearch<T, U, R>(
  arr: T[],
  compare1: (mid: number) => boolean,
  compare2: (mid: number) => boolean,
  succeed: (mid: number) => R,
  failure: (right: number) => R,
) {
  let left = 0,
    right = arr.length - 1
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2)
    if (compare1(mid)) {
      right = mid - 1
    } else if (compare2(mid)) {
      left = mid + 1
    } else {
      return succeed(mid)
    }
  }
  return failure(right)
}

Case

test.each([
  {
    matrix: [
      [1, 3, 5, 7],
      [10, 11, 16, 20],
      [23, 30, 34, 60],
    ],
    target: 3,
    result: true,
  },
  {
    matrix: [
      [1, 3, 5, 7],
      [10, 11, 16, 20],
      [23, 30, 34, 60],
    ],
    target: 13,
    result: false,
  },
  { matrix: [[1]], target: 1, result: true },
  { matrix: [[1]], target: 2, result: false },
])('matrix = $matrix,target = $target', ({ matrix, target, result }) => {
  expect(searchMatrix(matrix, target)).toBe(result)
})