杨氏矩阵中的二分查找算法实现

????????在计算机科学与编程中，我们经常遇到在特定数据结构中查找特定元素的问题。本篇博客将解析一个利用有序矩阵（杨氏矩阵）特性进行查找的程序实例，并通过可视化方式展示其实现过程。

一、问题背景

给定一个大小为?row?行和?col?列的杨氏矩阵（每行从左到右递增，且每列从上到下递增），编写一个名为?matrix?的函数来判断并找到整数?k?是否存在于该矩阵中。同时，当找到目标值时，返回其所在的行索引和列索引。

int matrix(int arr[row][col], int k, int *px, int *py);

二、算法思路

• 初始化指针：设置两个指针变量?x?和?y，分别指向矩阵的第一行（索引为0）和最后一列（索引为?col - 1）。
• 二分搜索策略：根据杨氏矩阵的特点，可以采用类似二分查找的方式来缩小搜索范围：
  • 如果当前元素?arr[x][y]?大于目标值?k，说明目标值可能位于当前元素左侧，因此将列索引?y?减一。
  • 如果当前元素小于目标值?k，说明目标值可能位于当前元素下方或右侧，此时将行索引?x?加一。
  • 当找到等于目标值的元素时，更新传入的指针地址所指向的位置，并返回1表示找到。

三、代码实现

int matrix(int arr[3][3], int k, int *px, int *py) {
    int x = 0;
    int y = *px - 1;

    while (x <= *px - 1 && y >= 0) {
        if (arr[x][y] > k) {
            y--;
        } else if (arr[x][y] < k) {
            x++;
        } else {
            *px = x;
            *py = y;
            return 1;
        }
    }
    return 0;
}

四、主函数示例及输出结果

int main() {
    // 初始化一个 3x3 的杨氏矩阵
    int arr[3][3] = { {1,2,3}, {4,5,6}, {7,8,9} };

    // 设置要查找的数字 k
    int k = 7;
    int x = 3; // 注意此处初始值不影响实际搜索过程
    int y = 3;

    // 调用 matrix 函数并获取返回值
    int ret = matrix(arr, k, &x, &y);

    // 输出结果
    if (ret == 1) {
        printf("yes ");
        printf("%d.%d", x, y); // 输出坐标
    } else {
        printf("no");
    }

    return 0;
}

五、可视化解释

假设我们要在以下矩阵中查找数字?7：

1 2 3
4 5 6
7 8 9

搜索过程如下：

1. 开始时，搜索指针位于?(0, 2)。
2. 因为?3 > 7，指针向左移至?(0, 1)。
3. 然后因为?2 < 7，指针向下移至?(1, 1)。
4. 再次比较，发现?5 < 7，指针继续向下移至?(1, 2)。
5. 此时，arr[1][2] = 7，找到目标值，返回?(1, 2)?并输出 "yes 1.2"。

通过上述算法，我们可以在时间复杂度低于?O(N)?的情况下高效地在杨氏矩阵中定位目标值。为了更好地理解这个过程，可以绘制一幅动态图来演示搜索路径的变化，但由于博客文本格式限制，这里无法直接提供动态图像，读者可以根据描述自行模拟这一过程。