Searching two-dimensional arrays in JavaScript (code example)

The content of this article is about searching for two-dimensional arrays in JavaScript (code examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

In a two-dimensional array (each one-dimensional array has the same length), each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom. Sort. Please complete a function, input such a two-dimensional array and an integer, and determine whether the array contains the integer.

Basic idea

The two-dimensional array is ordered, such as the following data:

1 2 3
4 5 6
7 8 9

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

Greater than: comparison and shift up

Less than: comparison and shift to the right

Code idea

Treat the two-dimensional array as a plane coordinate system

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

The target value is greater than the coordinate value---x coordinate 1

The target value is less than the coordinate value- --y coordinate-1

Note:

In the two-dimensional array arri,

j represents the x coordinate

i represents the y coordinate

Code

    function Find(target, array) {
      let i = array.length - 1; // y坐标
      let j = 0; // x坐标
      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 must be in order.

Compare with the midpoint value of the linear table. If it is small, continue to search in the small sequence, and recurse 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);
        }
    }

The above is the detailed content of Searching two-dimensional arrays in JavaScript (code example). For more information, please follow other related articles on the PHP Chinese website!