Monday, 5 June 2017

Search a 2D Matrix I

This matrix has the following properties:
        1. Integers in each row are sorted from left to right.
        2. The first integer of each row is greater than or equal to the last integer of the previous row.
    Example:
    [
        [1,   3,  5,  7],
        [10, 11, 16, 20],
        [23, 30, 34, 50]
    ]
    Given target = 3, return 1 ( 1 corresponds to true )

Return 0 / 1 ( 0 if the element is not present, 1 if the element is present ) for this problem

Approach : Use binary search to first find the row number then use binary search in that row to find the exact cell.




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
using namespace std;

bool searchMatrix(int matrix[][4], int matrixRowSize, int matrixColSize, int target) {
    int mid;
    int low = 0, row;
    int high = matrixRowSize - 1;
    row = -1;
    while(low <= high){
        mid = (low + high) / 2;
        if(target <= matrix[mid][matrixColSize - 1] && target >= matrix[mid][0]){
            row = mid;
            break;
        }else if(target < matrix[mid][0]){
            high = mid - 1;
        }else if(target > matrix[mid][matrixColSize - 1]){
            low = mid + 1;
        }
    }
    low = 0; high = matrixColSize - 1;
    if(row != -1){
        while(low <= high){
            mid = (low + high) / 2;
            if(matrix[row][mid] == target){
                return true;
            }else if(matrix[row][mid] < target){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
    }
    return false;
}

int main(){
    int matrix[3][4] = {
                    {1,   3,  5,  7},
                    {10, 11, 16, 20},
                    {23, 30, 34, 50}
                };
    cout << searchMatrix(matrix, 3, 4, 3);
    return 0;
}
Share:

0 comments:

Post a Comment

Contact Me

Name

Email *

Message *

Popular Posts