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

本文主要是介绍杨氏矩阵中的二分查找算法实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

一、问题背景

给定一个大小为 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} };// 设置要查找的数字 kint 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;
}