【4】在矩阵中查找是否存在某个数

骑猪看日落 2022-05-27 05:24 218阅读 0赞

## 在二维数组中查找 某一元素 ##

**1、题目：**在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按  
照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个  
整数，判断数组中是否含有该整数。

**2、分析：**选定数组中右上角或者（左下角）元素，与待查找的数字进行比较，如果待查找数字大于右上角元素，行数加1，继续比较；如果待查找数字小于右上角元素，列数减一再比较，这样每次比较完，都会少掉一行或者一列，时间复杂度为O(n);

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int Find(int*matrix,int rows,int cols,int findkey)
    {
        int found = -1;
        if(matrix == NULL ||rows < 0 || cols < 0)
        {
            return found;
        }
        if(matrix != NULL ||rows > 0 || cols > 0)
        {
            int row = 0;
            int col = cols - 1;
            while(col >= 0 && row < rows)
            {
                if(matrix[row*cols+col] == findkey)
                {
                    found = 1;
                    break;
                }
                else
                {
                    if(matrix[row*cols+col] > findkey)
                    {
                        --col;
                    }
                    else ++row;
                }
            }
        }
        return found;
    }
    
    
    
    //===================测试代码=================
    void test(int* matrix,int rows,int cols,int findkey)
    {
        if(matrix == NULL || rows <= 0 ||cols<= 0)
        {
            printf("参数出现传送错误\n");
            return ;
        }
        int ret = 0;
        ret = Find(matrix, M, N, findkey);
            if(ret == -1)
            {
                printf("查找的数字在本数组中不存在\n");
            }
            else
            printf("存在\n");
    
    
    }
    //================存在于数组中的三种情况=====================
    //1.数组中存在待查找的数字min< 10<max
    void test1()
    {
        int arr[][4] = {
       {
       1,2,8,9}, 
                        {
       2,4,9,12},
                        {
       4,7,10,13},
                        {
       6,8,11,15}};
        int findkey = 10;
        printf("test1()中情况：findkey= %d ",findkey);
        test((int* )arr,4,4,findkey);
    }
    //2.数组中存在待查找的数字min
    void test2()
    {
        int arr[][4] = {
       {
       1,2,8,9}, 
                        {
       2,4,9,12},
                        {
       4,7,10,13},
                        {
       6,8,11,15}};
        int findkey = 1;
        printf("\ntest2()中情况：：findkey= %d ",findkey);
        test((int* )arr,4,4,findkey);
    }
    //3.数组中存在待查找的数字max
    void test3()
    {
        int arr[][4] = {
       {
       1,2,8,9}, 
                        {
       2,4,9,12},
                        {
       4,7,10,13},
                        {
       6,8,11,15}};
        int findkey = 15;
        printf("\ntest3()中情况：findkey= %d ",findkey);
        test((int* )arr,4,4,findkey);
    }
    //===============================不存在的三种情况===================
    //4.数组中不存在待查找的数字，findkey<min
    void test4()
    {
        int arr[][4] = {
       {
       1,2,8,9}, 
                        {
       2,4,9,12},
                        {
       4,7,10,13},
                        {
       6,8,11,15}};
        int findkey = -1;
        printf("\ntest4()中情况：findkey= %d ",findkey);
        test((int* )arr,4,4,findkey);
    }
    //5.数组中不存在待查找的数字，findkey>max
    void test5()
    {
        int arr[][4] = {
       {
       1,2,8,9}, 
                        {
       2,4,9,12},
                        {
       4,7,10,13},
                        {
       6,8,11,15}};
        int findkey = 16;
        printf("\ntest5()中情况：findkey= %d ",findkey);
        test((int* )arr,4,4,findkey);
    }
    //6.数组中不存在待查找的数字，min<findkey<max
    void test6()
    {
        int arr[][4] = {
       {
       1,2,8,9}, 
                        {
       2,4,9,12},
                        {
       4,7,10,13},
                        {
       6,8,11,15}};
        int findkey = 5;
        printf("\ntest6()中情况：findkey= %d ",findkey);
        test((int* )arr,4,4,findkey);
    }
    
    //=========================测试代码的鲁棒性================
    void test7()
    {
        int arr[][4] = {
       {
       1,2,8,9}, 
                        {
       2,4,9,12},
                        {
       4,7,10,13},
                        {
       6,8,11,15}};
        int findkey = 1;
        printf("\ntest7()中情况：");
        test(NULL,4,4,findkey);
    }
    int main()
    {
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
        return 0;
    }

![70][]

[70]: /images/20220527/1b2ab55cff6a4527a2e3011245e5e09c.png