Binary search of 2D matrix

Question

I have written code as below:

bool binary_search(const std::vector<int>& v, const int& target) {
 int left = 0, right = v.size() - 1;
 while (left <= right) {
 int mid = left + (right - left) / 2;
 if (v[mid] == target)
 return true;
 if (target > v[mid])
 left = mid + 1;
 else
 right = mid - 1;
 }
 return false;
}
bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
 const int n = matrix.size();
 for (int i = 0; i < n; i++) {
 if (target <= matrix[i][matrix[i].size() - 1])
 return binary_search(matrix[i], target);
 }
 return false;
}

It returns true if the target is found in matrix, and false when is not present.

The matrix has following properties:

1. Each row is sorted in non-decreasing order.
2. The first integer of each row is greater than the last integer of the previous row.

Due to these properties, the binary_search will be invoked only once.

The task was to create O(log(mn)) algorithm. But I'm pretty sure that this is O(n + log m). So I'm looking to improve its computational complexity.

• Cris Luengo: It looks like it’s O(n + log m). If you use a binary search to find the row, instead of the linear search you have now, you’ll get O(log nm).
• Toby Speight: Please present complete code for review. It's much easier if we don't have to infer your #includes and main().

Answer 1

You clearly need to enable more compiler warnings. For example, we want to know about the dangerous conversion in

int right = v.size() - 1;

Since v.size() returns a std::size_t, this is almost certainly a narrowing conversion, and may even give a negative value in right.

Your binary_search() function could be completely eliminated by using std::binary_search() instead. Don't reinvent wheels!

The linear search of rows (for (int i = 0; i < n; i++)) would be simpler using a range-based for. But we don't want that - we should be using binary search to find the required row.

We should be passing a reference to const vector into searchMatrix(), since we don't intend to modify its values.

• Szyszka947: What about complexity? Can it be improved?
• Toby Speight: Yes - as said, use binary search rather than linear search when looking for rows.
• Szyszka947: Ah, sorry. I was reading in a hurry and somehow missed it