[Sword Refers to Offer] 1. Two-dimensional Array Search

  algorithm, array, Front end, Interview, javascript

subject

In a two-dimensional array (each one-dimensional array has 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. Please complete a function and enter such a two-dimensional array and an integer to determine whether the array contains the integer.

Basic idea

Two-dimensional arrays are ordered, such as the following data:

1 2 3
4 5 6
7 8 9

You can directly use the number in the lower left corner to start searching:

Greater than: Compare Up

Less than: compare right shift

Code thinking

Think of a two-dimensional array as a plane coordinate system

Starting from the lower left corner (0,arr.length-1):

Target value is greater than coordinate value —x coordinate +1

Target value is less than coordinate value —y coordinate -1

Note:

In the two-dimensional array arri

J stands for x coordinate.

I stands for y coordinate.

Code

function Find(target, array) {
 let i = array.length - 1;  // y coordinate
 let j = 0;  // x coordinate
 return compare(target, array, i, j);
 }
 
 function compare(target, array, i, j) {
 if (array[i] === undefined || array[i][j] === undefined) {
 return false;
 }
 const temp = array[i][j];
 if (target === temp) {
 return true;
 }
 else if (target > temp) {
 return compare(target, array, i, j+1);
 }
 else if (target < temp) {
 return compare(target, array, i-1, j);
 }
 }

Expansion: binary search

The condition of binary search is that it must be orderly.

Compared with the mid-point value of the linear table, if it is small, continue searching in the small sequence, and recursively until the same value is found.

function binarySearch(data, arr, start, end) {
 if (start > end) {
 return -1;
 }
 var mid = Math.floor((end + start) / 2);
 if (data == arr[mid]) {
 return mid;
 } else if (data < arr[mid]) {
 return binarySearch(data, arr, start, mid - 1);
 } else {
 return binarySearch(data, arr, mid + 1, end);
 }
 }