Interview Classic 150 Questions P74 Search a 2D Matrix

---

Timeline

Timeline

2025-12-02

init

Divide and Conquer

---

Problem:

P74 Search a 2D Matrix

https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-interview-150

Just treat the 2D matrix as 1D.

#include <vector>
using std::vector;

class Solution {
    public:
	bool searchMatrix(vector<vector<int> > &matrix, int target)
	{
		int m = matrix.size(), n = matrix[0].size();
		int left = 0, right = m * n - 1;
		int mid;
		int mid_i, mid_j;

		while (left <= right) {
			mid = (left + right) / 2;
			mid_i = mid / n;
			mid_j = mid % n;
			if (matrix[mid_i][mid_j] == target) {
				return true;
			} else if (matrix[mid_i][mid_j] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return false;
	}
};

leetcode hot100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        bool binary_search(vector<int> nums, int target)
        {
                int n = nums.size();
                int left = 0, right = n - 1, mid;

                while (left <= right) {
                        mid = left + (right - left) / 2;

                        if (nums[mid] < target)
                                left = mid + 1;
                        else if (nums[mid] > target)
                                right = mid - 1;
                        else
                                return true;
                }

                return false;
        }

    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target)
        {
                int i, m = matrix.size();
                for (i = 0; i < m; i++) {
                        if (target >= matrix[i].front() && target <= matrix[i].back())
                                return binary_search(matrix[i], target);
                }

                return false;
        }
};