Day3. Two-dimensional array search

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.

My solution

Train of thought

Starting at the top left corner, it increases to the right/down. Let me do it in a loop.

Loop condition: The array does not overflow and the current value is less than the target value

1. Select the current value
2. Compares the current value with the target value
3. Decide where to go next, or find out
   • The current value is the same as the target value
   • The value on the right is small, so the next step is to the right
   • The bottom value is smaller, and then we go down
   • To the border, only go one way

Question:

1. It is possible that the right-hand value is small, but the lower value is the target value
2. There may be cases where the right-hand value is small, but below the target value

Solution:

1. Add the conditional judgment, “the value on the right is small && the value below is not the target value, the next step is to the right”
2. It can’t be solved. There’s something wrong with the algorithm

Code:

function find(target, array) {
  debugger
  const row = array.length
  const col = array[0].length
  let rp = 0
  let cp = 0
  if (row === 0 || col === 0) {
    return false
  } else if (array[0] [0] > target || array[row - 1][col - 1] < target) {
    return false
  } else {
    while (rp < row && cp < col && array[rp][cp] <= target) {
      // Loop when array[rp][cp] does not overflow and is less than the target value
      if (array[rp][cp] === target) {
        return true
      } else if (rp + 1 === row) {
        // If you reach the last row, increase the number of columns at a time
        cp++
      } else if (cp + 1 === col) {
        // If you reach the last column, increase the number of rows at a time
        rp++
      } else if (array[rp + 1][cp] <= array[rp][cp + 1] && array[rp][cp + 1] !== target) {
        // Move in the direction of small increments, and the other direction is not the target result
        rp++
      } else {
        cp++
      }
    }
    return false}}Copy the code

The right solution

Train of thought

Starting at the upper right corner of the array, if the target value is less than the current value, the next step is to the right; If the target value is greater than the current value, the next step is down.

1. Initialize the location to select
2. Loop condition: No overflow occurred at the location to be selected
3. Get the current value
4. Compares the current value with the target value
   • If the same, return
   • The target value is greater than the current value, go down
   • If the target value is less than the current value, go left

Analysis of the

Similar to the previous algorithm, each move is equivalent to deleting a row/column (moving down deletes a row, moving to the left deletes a column), but there is no way to ensure that the deleted row/column does not have the target value.

This algorithm is similar to binary search, the target value is greater than the current value, smaller than the current value can be omitted; The target value is less than the current value, and anything larger than the current value can be omitted.

implementation

function find(array, target) {
  const row = array.length
  const col = array[0].length
  let rp = 0
  let cp = col - 1
  let current
  while (rp < row && cp >= 0) {
    current = array[rp][cp]
    if (current === target) {
      return true
    } else if (current < target) {
      rp++
    } else {
      cp--
    }
  }
  return false
}
Copy the code

conclusion

While loop idea

1. Initialize the selection criteria
2. Judgment cycle condition
3. Select the initialized value based on the selection criteria
4. Branch statements modify selection criteria

So the code looks like this

Initialize the selection condition while(){** select ** if(){modify selection condition} else if(){modify selection condition} else {return}} returnCopy the code