/***************************************************** file: young_matrix.c brief:find a key in the young matrix which keeps a increase order in row and col 2015.1.3 yejing 1.0 creat file *****************************************************/ #include <stdio.h> #include <stdlib.h> /* 朴素杨氏矩阵查找 主要依赖其堆序性质,从左下角或者右上角开始 */ int young_matrix_search_normal(int array[][4], int tgt){ int tmp = array[0][3]; int i = 0, j = 3; do{ if(tgt == tmp){ printf("%s:x = %d, y = %d \n",__func__, i + 1, j + 1); return 1; } else if(tgt < tmp && j > 0) tmp = array[i][--j]; else if(tgt > tmp && i < 3) tmp = array[++i][j]; else return 0; }while(1); } /* 二分杨氏矩阵查找 先计算中间点,比中间点小的查左上角矩阵,大的查另外三个矩阵 */ int young_matrix_binary_search(int array[][4], int start_x, int start_y, int end_x, int end_y, int tgt){ int middle_x, middle_y; middle_x = (start_x + end_x)/2; middle_y = (start_y + end_y)/2; int middle = array[middle_x][middle_y]; if(tgt == middle){ printf("%s:x = %d, y = %d \n",__func__, middle_x + 1, middle_y + 1); return 1; }else if(middle_x == start_x && middle_y == start_y){ //printf("search failed, no key:%d \n", tgt); return 0; } else if(middle > tgt) young_matrix_binary_search(array, start_x, start_y, middle_x, middle_y, tgt); else if(middle < tgt){ young_matrix_binary_search(array, middle_x, middle_y, end_x, end_y, tgt); young_matrix_binary_search(array, start_x, middle_y, middle_x, end_y, tgt); young_matrix_binary_search(array, middle_x, start_y, end_x, middle_y, tgt); } } int main(int argc, char* argv[]){ int array[][4] = { {1, 4, 7, 10}, {2, 5, 8, 11}, {3, 6, 9, 12}, {4, 7, 10, 13}, }; young_matrix_search_normal(array, 9); young_matrix_binary_search(array,0, 0, 3, 3, 9); return 1; }