“This is the first day of my participation in the August More Text Challenge.

The problem describes that 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.

If the value is greater than (m+n) 3, go to the left. If the value is smaller than (m+n) 3, go to the left. You start at the bottom left corner, if it’s greater than it goes up, if it’s less than it goes right (m+n) 4. Search each row with binary search (mlogn) 5. Binary search rule (row and column are binary) (no) (logm*logn)

1. Violent solution

function find(target,array) {
    for(var i=0; i<array.length; i++) {
        for(var j=0; j<array[i].length; j++) {
            if(array[i][j] == target) {
                console.log('Found successfully:',array[i][j])
                return true}}}return false;
}
// Define and initialize
var treeCol=new Array(a);for(var i=0; i<2; i++){ treeCol[i]=new Array(a); }/ / assignment
treeCol[0] [0] ="1";
treeCol[0] [1] ="2";
treeCol[1] [0] ="3"; 
treeCol[1] [1] ="4";
find('4',treeCol)
Copy the code

2. Search from the upper right corner

function find(target,array) {
    var m = array.length;
    var n =array[0].length;
    var j = n-1;
    var i = 0;
    while(j >= 0 && i<m) {
        if(array[i][j] > target) {
            j--
        } else if(array[i][j] < target) {
            i++
        } else if(array[i][j] == target) {
            return true
        }
        console.log('Find success value is:'+ array[i][j])
    }
        return false
}
// Define and initialize
var treeCol=new Array(a);for(var i=0; i<2; i++){ treeCol[i]=new Array(a); }/ / assignment
treeCol[0] [0] ="1";
treeCol[0] [1] ="2";
treeCol[1] [0] ="3"; 
treeCol[1] [1] ="4";
find('4',treeCol)
Copy the code

3. Search from the lower left corner

function find(target,array) {
    var m = array.length;
    var n =array[0].length;
    var j = 0;
    var i = m-1;
    while(j >= 0 && i<n) {
        if(array[i][j] > target) {
            i--
        } else if(array[i][j] < target) {
            j++
        } else if(array[i][j] == target) {
            return true
        }
        console.log('Find success value is:'+ array[i][j])
    }
        return false
}
// Define and initialize
var treeCol=new Array(a);for(var i=0; i<2; i++){ treeCol[i]=new Array(a); }/ / assignment
treeCol[0] [0] ="1";
treeCol[0] [1] ="2";
treeCol[1] [0] ="3"; 
treeCol[1] [1] ="4";
find('4',treeCol)
Copy the code

4. Use binary search

// If the array is sorted (assuming the sequence is sorted from smallest to largest)
function find(target,array) {
    for(var i=0; i<array.length ; i++) {
        var left = 0;
        var right = array[0].length;
        mid = Math.floor((left + right)/2);
        while(left <= right) {
            if(array[i][mid] > target) {
                right = mid
            } else if(array[i][mid] < target) {
                left = mid+1
            } else if(array[i][mid] == target) {
                console.log('Find success value is:'+ array[i][mid])
                return true}}}return false;
}
// Define and initialize
var treeCol=new Array(a);for(var i=0; i<2; i++){ treeCol[i]=new Array(a); }/ / assignment
treeCol[0] [0] ="1";
treeCol[0] [1] ="2";
treeCol[1] [0] ="3"; 
treeCol[1] [1] ="4";
find('4',treeCol)
Copy the code