问题：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
- 选取数组中右上角的数字
- 如果数字等于要查找的数字，游戏结束
- 如果数字大于要查找的数字，剔除这个数字所在的列
- 如果数字小于要查找的数字，剔除这个数字所在的行
- 每一步都在缩小范围，直到最终找到查找的数字，或者查找范围为空。
代码实现
#include <iostream>
#include "vector"
#include <iomanip>
using namespace std;
// 利用搜索的方法
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int rows = array.size();
int cols = array[0].size();
int locationX = 0;
int locationY = cols-1;
while (locationX < rows && locationY >=0) {
if (array[locationX][locationY] == target) {
return true;
}
else if (array[locationX][locationY] > target) {
--locationY;
}
else {
++locationX;
}
}
return false;
}
};
// 利用二分查找的方法
class DSolution {
public:
bool binFind(int target, vector<vector<int> > array) {
int rows = array.size();
int cols = array[0].size();
for(int i=0;i<rows;i++){
int low=0;
int high=cols-1;
while(low<=high){
int mid=(low+high)/2;
if(target == array[i][mid])
return true;
else if(target<array[i][mid])
high=mid;
else
low=mid+1;
}
}
return false;
}
};
int main(int argc, char const *argv[])
{
int arr[4][4] = {
1,2,8,9,
2,4,9,12,
4,7,10,13,
6,8,11,15
};
vector<vector<int> > array(4);
array.resize(4);
for (int i = 0; i < 4; i++)
{
array[i].resize(4);
}
for (int m = 0; m < 4; m++)
{
for (int n = 0; n < 4; n++)
{
array[m][n] = arr[m][n];
}
}
for (int m = 0; m < 4; m++)
{
for (int n = 0; n < 4; n++)
{
cout<<setw(3)<<array[m][n];
}
cout << "\n";
}
DSolution solution;
int t = solution.binFind(6, array);
cout << t;
return 0;
}
附录
关于二分查找的实现方法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int ddbsearch(int *A, int x, int y, int v)
{
int m;
while (x<=y) {
m = (x+y)/2;
if (A[m] == v) return 1;
else if (A[m] > v) y = m;
else x = m+1;
}
return -1;
}
int main(int argc, char const *argv[])
{
int a[4] = {1,2,3,4};
printf("%d\n", ddbsearch(a,0,3,4));
return 0;
}
