西南交大swjtu算法实验4.2|分治

1. 实验目的

编写一个分治算法来搜索 m*n 矩阵 matrix 中的一个目标值 target，该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。通过该实例熟悉分治算法的分析求解过程，时间复杂度分析方法，以及如何设计分治算法解决实际问题。

2. 实验任务

实验预习:

(1）采用二分搜索策略实现问题求解程序，验证输入输出结果，并对下述三种设计算法的时间复杂度进行对比分析: 方法一:蛮力法，对于每一行可以像搜索未排序的一维数组——通过检查每个元素来判断是否有目标值。方法二:二分法搜索策略，矩阵已经排过序，可以采用二分查找加快搜索效率(通过行列切片)。方法三:搜索空间缩减策略，可以将已排序的二维矩阵划分为四个子矩阵，其中两个可能包含目标，其中两个肯定不包含，进一步提升问题的求解效率。 (2)编写程序实现上述算法。

上机实验:

(3）上机实验，验证样例输入时程序的执行过程以及算法复杂度分析结果与实际运行时间是否一致。 (4）撰写相应的实验报告，实验报告内容包括:实验目的、实验任务、实验环境、实验步骤、实验结果及其分析以及实验总结等部分内容。

4. 实验步骤及结果

4.1 实验预习

4.1.1 时间复杂度分析

方法一:蛮力法，时间复杂度：O(m*n)。

方法二:二分法搜索策略，O(mlogn)

方法三:搜索空间缩减策略，O(logm*logn)

方法四：z 字型搜索，O(m+n)

4.1.2 程序实现

#include <iostream>
using namespace std;
#define Max 10
int matrix[Max][Max];
bool allsearch(int target,int m,int n)
{
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
           if (matrix[i][j] == target) {
                return true;
            }
 
        }
    }
    return false;
}
 
 
bool bsearch(int target, int line,int n)
{
        int l = 0; int r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[line][mid] >= target) { r = mid; }
            else { l = mid + 1; }
        }
        if (matrix[line][l] == target) return true;
        return false;
    }
bool searchMatrix(int target,int m,int n)
{
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] > target) { break; }
            if (matrix[i][n] < target) { continue; }
            if (bsearch(target, i,n) == true) return true;
        }
        return false;
 }
 
 
bool DropSpaceSearch(int target, int left, int right, int up, int down)
{
    if (left > right || up > down)
        return false;
    if (target<matrix[up][left] || target>matrix[down][right])
        return false;
    int mid = (left + right) /2;
    int index = up;
    while (index <= down && matrix[index][mid] <= target) {
        if (matrix[index][mid] == target)
            return true;
        index++;
    }
    return DropSpaceSearch(target, left, mid - 1, index, down) || DropSpaceSearch(target, mid + 1, right, up, index - 1);
}
bool myfind(int m, int n, int target) //z字型搜索,总搜索次数为 m + n。在这之后，x 和 y 就会超出矩阵的边界。
{
 
    int x = 0, y = n - 1;
    while (x < m && y >= 0) {
        if (matrix[x][y] == target) {
            return true;
        }
        if (matrix[x][y] > target) {
            --y;
        }
        else {
            ++x;
        }
    }
    return false;
}
 
int main() {
    int target;
    int n, m;
    cout << "输入矩阵行数和列数:";
    cin >> m >> n;
    cout << "输入矩阵:";
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    cout << "输入target:";
    cin >> target;
    cout << "遍历法:";
    if (allsearch(target,m - 1,n - 1))
        cout << "true" << endl;
    else
        cout << "false" << endl;
    cout << "二分法:";
    if (searchMatrix(target, m - 1, n - 1))
        cout << "true" << endl;
    else
        cout << "false" << endl;
    cout << "搜索空间缩减法:";
    if (DropSpaceSearch(target, 0, m - 1, 0, n - 1))
        cout << "true" << endl;
    else
        cout << "false" << endl;
    cout << "z字型搜索:";
    if (myfind(m - 1, n - 1, target))
        cout << "true" << endl;
    else
        cout << "false" << endl;
 
    return 0;
}