The actual problem is pretty simple, implement an algorithm that returns true if the target value is contained within the matrix. Here are the two solutions I came up with. I'm not sure which one would be preferable? I believe solution 1 is faster since we don't need to build a new array, however would this be significantly faster?

Solution 1:

var searchMatrix = function(matrix, target) {
    let cols = matrix[0].length;
    let rows = matrix.length;
    let left = 0; 
    let right = cols*rows - 1;
    
    while(left <= right) {
        let midIndex = left + Math.floor((right-left)/2);
        let midValue = matrix[Math.floor(midIndex/cols)][Math.floor(midIndex%cols)];
        console.log(midValue);
        if(midValue === target) {
            return true;
        }
        else if(midValue < target) {
            left = midIndex + 1;
        } else {
            right = midIndex - 1;
        }
    }
    return false;
};

Solution 2:

var searchMatrix = function(matrix, target) {
    let arr = []
    for(let row of matrix) {
        arr = [...arr,...row];
    }
    let left = 0;
    let right = arr.length - 1;
    
    while(left <= right) {
        let middle = left + Math.floor((right-left)/2);
        if(arr[middle] === target) {
            return true;
        } else if(arr[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
        
    return false;
};

Based on my understanding, the main step we're adding is converting the matrix into a regular Array. Would this make the algorithm O(n) since we have to add every element into the new array?

For solution 1, we don't have to create a new array so we'd have constant space correct? I'm not particularly sure how to explain the first solution is preferable in terms of time/space.