In this article we will see some implementation problems of binary search. Before you see and learn the solution, try to solve it on your own. Just understand the problem and try to solve it on your own. Let’s get started!
Table of Contents
Count Negative Numbers in a Sorted Matrix
Problem – Given a m * n
matrix grid
which is sorted in non-increasing order both row-wise and column-wise. Return the number of negative numbers in grid
using Binary search in this problem
Example 1:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.
Example 2:
Input: grid = [[3,2],[1,0]]
Output: 0
Example 3:
Input: grid = [[1,-1],[-1,-1]]
Output: 3
Example 4:
Input: grid = [[-1]]
Output: 1
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 100
- -100 <= grid[i][j] <= 100
Solution
According to size, if we go in linear fashion, that is, Check each cell of matrix one by one the time complexity is O (m*n) which is affordbale if m and n less then 100
But if we try to do it in O(m*log(n)) time, We have to use Binary Search, which is better approach.
Linear Search Solution
Algorithm –
Simply traverse one by one each cell of matrix and increase count if the value is negative
int countNegatives(vector<vector<int>>& grid) {
int ans = 0;
for(int i =0;i<grid.size();i++)
{
for(int j = 0;j<grid[i].size();j++)
if(grid[i][j]<0)
ans++;
}
return ans;
}
Time Complexity
Time Complexity – O(no of rows* no of column)
Binary Search Solution
As we know, Binary search is a divide and conquer algorithm, so, we are going to focus on dividing each row of the array in this problem
- Traverse each row one by one
- Do a Binary search to find the first negative element index
- Subtract the length of row by index to find the total number of a negative number, because elements are arranged in descending order
- Repeat Until any row left
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int ans = 0;
for(int i =0;i<grid.size();i++)
{
ans+=binarySearch(grid[i]); // Traversing each row one by one
}
return ans;
}
int binarySearch(vector<int> &bs)
{
int l = 0;
int r = bs.size()-1;
while(l<=r)
{
int mid = (l+r)/2;
if(bs[mid]<0)
{ // for finding negative element
r = mid-1;
}
else
l = mid+1;
}
if(l<bs.size() && bs[l]<0)
return bs.size()-l; // return number of negative element
else
return 0;
}
};
Explanation:
- We will solve the problem using class. Assign the traversing operation in a separate function.
- Now in a separate function write the binary search condition. (Separating the list into two different parts).
- For separating the list, we find the middle element and assign the left and right according to the middle element.
- This is the implementation we did in the above code.
Time complexity
Time Complexity = O(no of rows * log( max of column ))
Which solution is better?
Whenever we perform any search operation in an array or list, it is always to follow binary search because it reduces time complexity. Always remember that a good code is the one with less time consumption. So for this problem too, follow binary search 🙂
Conclusion
In this article we have seen a problem regarding binary search. We also learnt the solution for the same problem in a linear search way too. We discussed the algorithm and solutions for both the ways. Hop this article helped. Leave your comments below to let us know if you have any queries!
https://waterfallmagazine.com
Wow! Finally I got a webpage from where I be able to really get helpful facts concerning my study and knowledge.
Have you ever considered publishing an e-book or guest authoring on other blogs?
I have a blog based on the same topics you discuss and would really like to have
you share some stories/information. I know my visitors
would enjoy your work. If you are even remotely interested, feel free to send me an email.