西南交通大学算法分析与设计实验4.2

实验要求：

 本文章只提供代码实现：

（1）蛮力法：

#include <iostream>

using namespace std;

#define MAX_SIZE 100

int sorted_matrix[MAX_SIZE][MAX_SIZE];
int n, m, target, dest_x = -1, dest_y = -1;

void Search(int i, int j) {
    if (i >= n || j >= m) {
        return ;
    }
    if (target == sorted_matrix[i][j]) {
        dest_x = i, dest_y = j;
        return ;
    }
    if (target >= sorted_matrix[i][j + 1]) {
        Search(i, j + 1);
    }
    if (target >= sorted_matrix[i + 1][j]) {
        Search(i + 1, j);
    }
}

int main() {
    cin >> n >> m >> target;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> sorted_matrix[i][j];
        }
    }
    Search(0, 0);
    if (dest_x < 0 || dest_y < 0) {
        cout << "Not Found" << endl;
        return 0;
    }
    cout << "Find target, Position: " << dest_x << "," << dest_y << endl;
    return 0;
}

（2）加入二分查找优化方法：

#include "iostream"

#define MAX_SIZE 100

using namespace std;

int sorted_matrix[MAX_SIZE][MAX_SIZE];
int n, m, target, dest_x = -1, dest_y = -1;

bool find(int array[], int left, int right) {
    int mid = (left + right) / 2;
    if (array[mid] == target) {
        dest_y = mid;
        return true;
    }
    if (right - left == 1) return false;
    if (array[mid] > target) {
        if (find(array, left, mid))
            return true;
    }
    if (array[mid] < target) {
        if (find(array, mid, right))
            return true;
    }
    return false;
}

bool Search() {
    for (int i = 0; i < n; i++) {
        if (sorted_matrix[i][m - 1] >= target && sorted_matrix[i][0] <= target) {
            if (find(sorted_matrix[i], 0, m)) {
                dest_x = i;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> target;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> sorted_matrix[i][j];
        }
    }
    if (Search()) {
        cout << "Find Target, Postion: " << dest_x << "," << dest_y << endl;
    } else {
        cout << "Not Found" << endl;
    }
    return 0;
}

（3）分块查找方法：

#include "iostream"

#define MAX_SIZE 100

using namespace std;

int sorted_matrix[MAX_SIZE][MAX_SIZE];
int n, m, target, dest_x = -1, dest_y = -1;

bool Search(int row_u, int row_d, int col_l, int col_r) {
    if (target < sorted_matrix[row_u][col_l])
        return false;
    if (target == sorted_matrix[row_u][col_l]) {
        dest_x = row_u;
        dest_y = col_l;
        return true;
    } else if (target == sorted_matrix[row_d][col_r]) {
        dest_x = row_d;
        dest_y = col_r;
        return true;
    }
    int row_m, col_m;
    row_m = (row_u + row_d) / 2;
    col_m = (col_l + col_r) / 2;
    if (target >= sorted_matrix[row_u][col_l] && target <= sorted_matrix[row_m][col_m]) {
        if (Search(row_u, row_m, col_l, col_m)) return true;
    }
    if (target >= sorted_matrix[row_m][col_l] && target <= sorted_matrix[row_d][col_m]) {
        if (Search(row_m, row_d, col_l, col_m)) return true;
    }
    if (target >= sorted_matrix[row_u][col_m] && target <= sorted_matrix[row_m][col_r]) {
        if (Search(row_u, row_m, col_m, col_r)) return true;
    }
    if (target >= sorted_matrix[row_m][col_m] && target <= sorted_matrix[row_d][col_r]) {
        if (Search(row_m, row_d, col_m, col_r)) return true;
    }
    return false;
}

int main() {
    cin >> n >> m >> target;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> sorted_matrix[i][j];
        }
    }
    if (Search(0, n - 1, 0, m - 1)) {
        cout << "Find Target, Position :" << dest_x << "," << dest_y << endl;
    } else {
        cout << "Not Found" << endl;
    }
    return 0;
}

输入样例：

5 5 30
1 4 7 11 15 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24 18 21 23 26 30

以上代码仅经过简单的样例测试，并不代表严格验证时能够正确运行，如有问题欢迎指出