二分查找:
十分简单,但编程珠玑上的说不要掉以轻心,so,写下来,以防万一:
int binary_search(int* a, int low, int high, int Num) { if(low > high) return -1; int middle = (low + high)/2; if(Num == a[middle]) return middle; else if(Num > a[middle]) binary_search(a, middle + 1, high, Num); else binary_search(a, low, middle - 1, Num); }
杨氏矩阵查找问题:
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字 6,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。
我直接实现的是方法 2、首先直接定位到最右上角的元素,再配以二分查找,比要找的数(6)大就往左走,要找数(6)的小就往下走,直到找到要找的数字(6)为止,如下图所示:
//代码
#define COL 4 #define ROW 4 bool young_matrix_search(int array[][COL], int Num) { int i = 0, j = COL-1; while(i >= 0 && i <= ROW - 1 && j >= 0 && j <= COL - 1) { if(array[i][j] == Num) return true; if(array[i][j] > Num) j--; if(array[i][j] < Num) i++; } return false; } #include <iostream> using namespace std; int main() { //int a[] = {1,3,5,7,9,12,45}; //binary_search(a, 0, sizeof(a)/sizeof(a[0]) - 1, 55); int a[ROW][COL] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}}; for (int i = 1; i <= 15; i++) { if (young_matrix_search(a, i)) cout<<"search:"<<i<<" hit!"<<endl; else cout<<"search:"<<i<<" miss!"<<endl; } }