Question

How to search a 2d matrix using binary search in C

Answer 1

#include <stdio.h>
#include <stdbool.h>

#define ROWS 3
#define COLS 4

bool searchMatrix(int matrix[][COLS], int rows, int cols, int target) {
    int start = 0;
    int end = rows * cols - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;

        // Map the 1D index to 2D indices
        int midValue = matrix[mid / cols][mid % cols];

        if (midValue == target) {
            return true; // Target found
        } else if (midValue < target) {
            start = mid + 1; // Search in the right half
        } else {
            end = mid - 1; // Search in the left half
        }
    }

    return false; // Target not found
}

int main() {
    int matrix[ROWS][COLS] = {
        { 1,  4,  6,  9},
        {11, 17, 18, 29},
        {32, 38, 40, 70}
    };

    int target = 17;

    if (searchMatrix(matrix, ROWS, COLS, target)) {
        printf("Target %d found in the matrix.\n", target);
    } else {
        printf("Target %d not found in the matrix.\n", target);
    }

    return 0;
}



/*
run:

Target 17 found in the matrix.

*/

 

70+ SQL courses for beginners and professionals