Category: Binary Search

Categories
Array Binary Search Leetcode Recursion

Search Matrix

let searchMatrix = function(matrix, target) {
    if(!matrix.length) return false;

    function search(startRow, endRow, startCol, endCol) {
        console.log(startRow, endRow, startCol, endCol);
        let midRow = Math.floor((startRow + endRow) / 2); //?
        let midCol = Math.floor((startCol + endCol) / 2); //?


        if (startRow < endRow && startCol < endCol) {
            const midValue = matrix[midRow][midCol]; //?
            if(midValue === target) {
                return true;
            }
            if (midValue < target) {
                return search(midRow + 1, endRow, startCol, endCol)
                        || search(startRow, endRow, midCol + 1, endCol);
            }
            else {
                return search(startRow, midRow, startCol, endCol)
                    || search(startRow, endRow, startCol, midCol);
            }
        }

        return false;
    }

    return search(0, matrix.length, 0, matrix[0].length);
};
Categories
Binary Search Recursion

Second highest number between two arrays

let secondHighest = function(arr1, arr2) {

    if (arr1.length === 1 && arr2.length === 1) {
        return Math.min(arr1[0], arr2[0]);
    }
    else if (arr1.length === 0 && arr2.length === 2) {
        return Math.min(arr2[0], arr2[1]);
    }
    else if (arr2.length === 0 && arr1.length === 2) {
        return Math.min(arr1[0], arr1[1]);
    }

    let mid1 = Math.ceil((arr1.length / 2) - 1)
    let mid2 = Math.ceil((arr2.length / 2) - 1);

    if (arr1[mid1] <= arr2[mid2]) {

        arr1 = arr1.slice(mid1 + 1);
        arr2 = arr2.slice(mid2);
    }
    else {
        arr1 = arr1.slice(mid1);
        arr2 = arr2.slice(mid2 + 1);
    }

    return secondHighest(arr1, arr2);
}
Categories
Binary Search Recursion

Binary Search

function binarySearch(arr, n, start = 0, end = arr.length) {
    let mid = Math.floor((end + start) / 2);
    if (arr[mid] === n) return mid;

    if (start < end - 1) {
        if (n > arr[mid]) {
            return binarySearch(arr, n, mid, end);
        } else {
            return binarySearch(arr, n, start, mid);
        }
    }
    return -1;
}