Binary Search Problem |LeetCode Problem – 1|Easy

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 – 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

  1. Traverse each row one by one
  2. Do a Binary search to find the first negative element index
  3. Subtract the length of row by index to find the total number of a negative number, because elements are arranged in descending order
  4. 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;
        
        
        
        
    }
};
Time Complexity  = O(no of rows * log( max of column ))       

Tagged : / / /

Binary Search

Binary Search

Binary Search is a searching algorithm for searching an element in a sorted list or array. This Algorithm is efficient than the Linear Search algorithm and performs the search operation in logarithmic time complexity for sorted arrays or lists.

Binary Search performs the search operation by repeatedly dividing the search interval in half. The idea is, to begin with, an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. continuously, check until the value is found or the interval is empty.

Problem: Given a sorted array arr[] of N elements, write a function to search a given element X in arr[] using Binary Search Algorithm

Algorithm

  • Compare X with the middle element of the array.
  • If X matches with middle element, we return the mid index.
  • Else If X is greater than the mid element, then X can only lie in the right half subarray after the mid element. So we will now look for X in only the right half ignoring the complete left half.
  • Else if X is smaller, search for X in the left half ignoring the right half.

Implementation


// A recursive binary search function. It returns 
// location of x in given array arr[l..r] if present, 
// otherwise -1 

// Initially,
// l = 0, first index of arr[].
// r = N-1, last index of arr[].
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 

An Iterative Binary Search Approach


// A iterative binary search function. It returns 
// location of x in given array arr[l..r] if present, 
// otherwise -1 

// Initially,
// l = 0, first index of arr[].
// r = N-1, last index of arr[].
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was 
    // not present 
    return -1; 
}

Time Complexity

O(log N), where N is the number of elements in the array

Practice Link – 1 LeetCode Problem Explanation

Tagged : /

Linear Search in C/C++

Linear Search

Linear Search in C/C++ means to sequentially traverse a given list or array and check if an element is present in the respective array or list. The idea is to start traversing the array and compare elements of the array one by one starting from the first element with the given element until a match is found or the end of the array is reached.

Examples :

Input : arr[] = {10, 20, 80, 30, 60, 50,
                     110, 100, 130, 170}
          key = 110;
Output : 6
Element 110 is present at index 6

Input : arr[] = {10, 20, 80, 30, 60, 50,
                     110, 100, 130, 170}
           key = 175;
Output : -1
Element 175 is not present in arr[].

Problem in Linear Search

Given an array arr[] of N elements, write a function for Linear Search in C to search a given element X in arr[].

Algorithm:

  • Start from the leftmost element of arr[] and one by one compare X with each element of arr[].
  • If X matches with an element, return the index.

If X doesn’t match with any of elements and end of the array is reached, return -1

// Function to linearly search the element X in the 
// array arr[] of N elements
int search(int arr[], int N, int X) 
{    
    // Pointer to traverse the array
    int i; 

    // Start traversing the array
    for (i = 0; i < N; i++) 
    {   
        // If a successful match is found,
        // return the index
        if (arr[i] == X) 
            return i; 
    }

    // If the element is not found,
    // and end of array is reached
    return -1; 
}

Time Complexity

O(N). Since we are traversing the complete array, so in worst case when the element X does not exists in the array, number of comparisons will be N. Therefore, worst case time complexity of the linear search algorithm is O(N).

Tagged : /