The title

In a two-dimensional array (each one-dimensional array is the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Complete a function that takes such a two-dimensional array and an integer and determines whether the integer is in the array

Train of thought

And since it’s sort from smallest to largest, think of binary search, loop over each row, binary search over each row.

/** * The class name, method name and parameter name have been specified, do not modify, * * @param target int @param array int 2 dimensional array * @return bool Bool */ export function Find(target: number, array: number[][]): boolean { // write code here if(array.length === 0) { return false } for(let i: number = 0; i < array.length; i++) { let l: number = 0 let r: number = array[0].length - 1 let mid: number; while(l <= r) { mid = Math.floor((l + r) / 2) if(array[i][mid] === target) { return true } if(array[i][mid] < target) { l = mid + 1 } else if (array[i][mid] > target) { r = mid - 1 } } } return false }Copy the code

extension

Binary search algorithm

const binarySearch = (arr, target) => {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] > target) {
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    }
  }

  return -1;
};

console.log(binarySearch([0, 1, 2, 3, 4, 5, 6], 1));
console.log(binarySearch([0, 1, 2, 3, 4, 5], 0));
Copy the code