Невозможно перебрать все строки в 2D-массиве при двоичном поиске по строкам

Когда вы заканчиваете строку, вы не сбрасываете start и end, поэтому следующая строка начинается с start и end в состоянии выхода и сразу же выходит.

int search2DArray(int matrix[][4], int n, int m, int key){
//    int start = 0, end = m-1; <<-- move this line 

    for(int i=0; i<n; i++){
        int start = 0, end = m-1; // <<-- to here
        while(start<=end){
            int mid = (start+end)/2;

            if (matrix[i][mid] == key){
                cout<<"FOUND\n";
                return 0;
            }else if (matrix[i][mid] < key){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }

    }
    cout<<"NOT FOUND\n";
    return -1;

}

Мы можем улучшить эту функцию с помощью старой доброй магии шаблонов C++:

template<size_t N, size_t M> // template deduction eliminates need for 
                             // m and n as parameters and arguments.
                             // code you don't have to write has no bugs.  
int search2DArray(int (&matrix)[N][M], int key)
{

    for (const auto & row : matrix) //range-based for loop allows easy 
                                    // processing of each row as a row
    {
        size_t start = 0; // split into two lines to make it harder to screw up.
        size_t end = M - 1; // using size_t because it can handle any array you 
                            // can give it.

        while (start <= end) // rest is pretty much the same
        {
            size_t mid = (start + end) / 2;

            if (row[mid] == key) // since we operate on rows we no longer 
                                 // care about the outer dimension
            {
                cout << "FOUND\n";
                return 0;
            }
            else if (row[mid] < key)
            {
                start = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
        }

    }
    cout << "NOT FOUND\n";
    return -1;

}

Эта версия будет называться примерно так:

int matrix[][4] = // compiler figures out the outer dimension
{                 // I don't have a good way to infer the inner dimension 
                  // without getting weirder than this problem requires.
    { 10, 20, 30, 40 },
    { 15, 25, 35, 45 },
    { 27, 29, 37, 48 },
    { 32, 33, 39, 50 } 
};

search2DArray(matrix, 29); // compiler figures out the template arguments 
                           // from the array

Примечание: многие распространенные проблемы с программным обеспечением уже решены в стандартной библиотеке C++. Использование std::binary_search и обобщение контейнера на итераторы с помощью std::begin и std::end позволяет сократить тело функции до

for (const auto & row : matrix) 
{
    if (std::binary_search(std::cbegin(row), 
                           std::cend(row), 
                           key))
    {
        std::cout << "FOUND\n";
        return 0;
    }
}
std::cout << "NOT FOUND\n";
return -1;

и использовать его для массивов и любого библиотечного контейнера (хотя для большинства контейнеров это не имеет смысла. Зачем двоичный поиск map?).