[坑] 大家来做题之二叉查找

2008/6/17镜像同步24 回复

这个题就是传说中错误率极高的二叉查找，大家必须小心谨慎不了解的同学可以Google/Baidu，或者参考数据结构与算法教程在bsearch的声明后进行实现，请仔细阅读函数说明，不要修改TEST CASE，贴出代码和运行结果 [QUOTE]#include<stdio.h> /** * 函数功能描述: Binary Search * 参数说明: int val 需要查询的数值 * int* array 待查询数组,升序排列 * int* steps 返回此次查询的循环次数,每次调用bsearch需将此变量重置为0 * int* result_index 返回搜索结果的索引,没有查询到返回-1 * 返回值: 异常情况返回-1 * 没有找到结果返回0 * 找到结果返回1 */ int bsearch(int val, int* array, int n, int* steps, int* result_index); int main() { int steps; int result_index; printf("\nCASE_01:\n"); int array1[] = {132, 222, 312, 423, 511, 612}; bsearch(12, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(24, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(355, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(4454, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(533, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(612, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-1, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); printf("\nCASE_02:\n"); int array2[] = {-100, 2, 3, 1000, 1005, 1006}; bsearch(1006, array2, sizeof(array2) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-200, array2, sizeof(array2) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(3, array2, sizeof(array2) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); printf("\nCASE_03:\n"); int array3[] = {1, 2, 3, 4, 5, 6}; bsearch(1, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(2, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(3, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(4, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(5, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(6, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(7, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); printf("\nCASE_04:\n"); int array4[] = {-3, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; bsearch(-1, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(2, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-3, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(4, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-5, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(6, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-7, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); printf("\nCASE_05:\n"); int *array5 = NULL; bsearch(1006, array5, sizeof(array5) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); array5 = array4; bsearch(-200, array5, 0, &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(3, array5, sizeof(array5) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); } [/QUOTE]

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

littleboy机器人#1 · 2008/6/17

算法基础为零。。我先学习下二叉查找是如何实现的。。。

jerrytian机器人#2 · 2008/6/17

[code] jerry@jerry:~/projects/C$ cat bsearch.c #include <stdio.h> int bsearch(int needle, int* intarr, int arrsize, int* steps, int* result) { *steps = 0; *result = -1; if (NULL == intarr || arrsize < 0) { return -1; } int low = 0, high = arrsize - 1; while (low <= high) { *steps = *steps+1; int mid = (low + high)/2; int ref = *(intarr + mid); if (ref == needle) { *result = mid; return 1; } if (ref < needle) { low = mid + 1; } else { high = mid - 1; } } return 0; } int main(void) { int steps; int result_index; printf("\nCASE_01:\n"); int array1[] = {132, 222, 312, 423, 511, 612}; bsearch(12, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(24, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(355, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(4454, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(533, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(612, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-1, array1, sizeof(array1) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); printf("\nCASE_02:\n"); int array2[] = {-100, 2, 3, 1000, 1005, 1006}; bsearch(1006, array2, sizeof(array2) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-200, array2, sizeof(array2) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(3, array2, sizeof(array2) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); printf("\nCASE_03:\n"); int array3[] = {1, 2, 3, 4, 5, 6}; bsearch(1, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(2, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(3, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(4, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(5, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(6, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(7, array3, sizeof(array3) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); printf("\nCASE_04:\n"); int array4[] = {-3, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; bsearch(-1, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(2, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-3, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(4, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-5, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(6, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(-7, array4, sizeof(array4) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); printf("\nCASE_05:\n"); int *array5 = NULL; bsearch(1006, array5, sizeof(array5) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); array5 = array4; bsearch(-200, array5, 0, &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); bsearch(3, array5, sizeof(array5) / sizeof(int), &steps, &result_index); printf("Steps: %d, Index: %d\n", steps, result_index); return 0; } jerry@jerry:~/projects/C$ gcc bsearch.c jerry@jerry:~/projects/C$ ./a.out CASE_01: Steps: 2, Index: -1 Steps: 2, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: 5 Steps: 2, Index: -1 CASE_02: Steps: 3, Index: 5 Steps: 2, Index: -1 Steps: 1, Index: 2 CASE_03: Steps: 2, Index: 0 Steps: 3, Index: 1 Steps: 1, Index: 2 Steps: 3, Index: 3 Steps: 2, Index: 4 Steps: 3, Index: 5 Steps: 3, Index: -1 CASE_04: Steps: 4, Index: 1 Steps: 3, Index: 3 Steps: 3, Index: 0 Steps: 1, Index: 5 Steps: 3, Index: -1 Steps: 4, Index: 7 Steps: 3, Index: -1 CASE_05: Steps: 0, Index: -1 Steps: 0, Index: -1 Steps: 1, Index: -1 [/code]

flyingmiao机器人#3 · 2008/6/17

发现其实问题不少-v-，调了好一会只会这个，就这么办了 int bsearch(int val, int* array, int n, int* steps, int* result_index) { if (!steps) return -1; *steps = 0; if (!result_index) return -1; *result_index = -1; if (!array) return - 1; int high = n - 1, low = 0; for (; low <= high && *result_index < 0; ++*steps) { int mid = (low + high) / 2; if (val == array[mid]) { *result_index = mid; } else if (val < array[mid]) high = mid - 1; else low = mid + 1; } if (*result_index > 0) return 1; return 0; } CASE_01: Steps: 2, Index: -1 Steps: 2, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: 5 Steps: 2, Index: -1 CASE_02: Steps: 3, Index: 5 Steps: 2, Index: -1 Steps: 1, Index: 2 CASE_03: Steps: 2, Index: 0 Steps: 3, Index: 1 Steps: 1, Index: 2 Steps: 3, Index: 3 Steps: 2, Index: 4 Steps: 3, Index: 5 Steps: 3, Index: -1 CASE_04: Steps: 4, Index: 1 Steps: 3, Index: 3 Steps: 3, Index: 0 Steps: 1, Index: 5 Steps: 3, Index: -1 Steps: 4, Index: 7 Steps: 3, Index: -1 CASE_05: Steps: 0, Index: -1 Steps: 0, Index: -1 Steps: 1, Index: -1

flyingkisser机器人#4 · 2008/6/17

2,X,z 【在 coolfantasy (Cool) 的大作中提到: 】 : 这个题就是传说中错误率极高的二叉查找，大家必须小心谨慎 : 不了解的同学可以Google/Baidu，或者参考数据结构与算法教程 : 在bsearch的声明后进行实现，请仔细阅读函数说明，不要修改TEST CASE，贴出代码和运行结果 : ...................

zwz机器人#5 · 2008/6/17

int bsearch(int val, int* array, int n, int* steps, int* result_index) { int low= 0, high= n-1, mid, find= 0; *steps= 0; if (array == NULL) return -1; for(int i=0;i<n-1;i++){ if (array[i] > array[i+1]) return -1; } CASE_01: Steps: 2, Index: -1 Steps: 2, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: -1 Steps: 3, Index: 5 Steps: 2, Index: -1 CASE_02: Steps: 3, Index: 5 Steps: 2, Index: -1 Steps: 1, Index: 2 CASE_03: Steps: 2, Index: 0 Steps: 3, Index: 1 Steps: 1, Index: 2 Steps: 3, Index: 3 Steps: 2, Index: 4 Steps: 3, Index: 5 Steps: 3, Index: -1 CASE_04: Steps: 4, Index: 1 Steps: 3, Index: 3 Steps: 3, Index: 0 Steps: 1, Index: 5 Steps: 3, Index: -1 Steps: 4, Index: 7 Steps: 3, Index: -1 CASE_05: Steps: 0, Index: -1 Steps: 0, Index: -1 Steps: 1, Index: -1 请按任意键继续. . . while (low <= high && !find){ mid= (low + high)/2; if (val < array[mid]) high= mid-1; else if (val > array[mid]) low= mid+1; else{ *result_index= mid; find= 1; } *steps= *steps+1; } if (!find){ *result_index= -1; return 0; } else{ return 1; } } 我开始很白痴的把二叉查找看成了生成二叉查找树，看了半天啥是二叉排序树 =。= 还好赶上了第一页末尾

wks机器人#6 · 2008/6/17

比较省脑子的递归法。不见得适合C语言。 int bsearch_recursive(int val, int* array, int low, int high, int *steps) { int mid; (*steps)++; if(low==high) { return -1; } else if(low+1==high) { if(array[low]==val) { return low; } else { return -1; } } else { mid=(low+high)/2; if(array[mid]>val) { return bsearch_recursive(val,array,low,mid,steps); } else { return bsearch_recursive(val,array,mid,high,steps); } } } int bsearch(int val, int* array, int n, int* steps, int* result_index) { /* This seems too ugly return steps==NULL?-1:result_index==NULL?-1: array==NULL?-1:n<0?-1:((*steps=0),(*result_index=bsearch_recursive(val,array,0,n,steps))==-1?0:1); */ if(steps==NULL || result_index==NULL || array==NULL || n<0) { return -1; } *steps=0; *result_index=bsearch_recursive(val,array,0,n,steps); if(*result_index==-1) { return 0; } else { return 1; } } CASE_01: Steps: 3, Index: -1 Steps: 3, Index: -1 Steps: 4, Index: -1 Steps: 4, Index: -1 Steps: 4, Index: -1 Steps: 4, Index: 5 Steps: 3, Index: -1 CASE_02: Steps: 4, Index: 5 Steps: 3, Index: -1 Steps: 4, Index: 2 CASE_03: Steps: 3, Index: 0 Steps: 4, Index: 1 Steps: 4, Index: 2 Steps: 3, Index: 3 Steps: 4, Index: 4 Steps: 4, Index: 5 Steps: 4, Index: -1 CASE_04: Steps: 5, Index: 1 Steps: 4, Index: 3 Steps: 4, Index: 0 Steps: 5, Index: 5 Steps: 4, Index: -1 Steps: 5, Index: 7 Steps: 4, Index: -1 CASE_05: Steps: 4, Index: -1 Steps: 1, Index: -1 Steps: 1, Index: -1

sunway机器人#7 · 2008/6/17

int bsearch(int val, int* array, int n, int* steps, int* result_index) { *steps=0; *result_index=-1; int from=0; int to=n-1; while (to>=from) { (*steps)++; int middle=(to+from)/2; if (val>array[middle]) { from=middle+1; } else if (val<array[middle]) { to=middle-1; } else { *result_index=middle; return 1; } } return 0; } case 5本身就有问题. 调用者应该保证n正确反映数组中元素的个数，对于int * array5=NULL,调用者应该保证n是0。这不是判不判断array==NULL的问题. 就像调用者给我的一个array,里面有5个元素，但他又告诉我里面有6个元素...让我怎么不出错... 【在 coolfantasy (Cool) 的大作中提到: 】 : 标题: [坑] 大家来做题之二叉查找 : 发信站: 北邮人论坛 (Tue Jun 17 11:57:50 2008), 站内 : : 这个题就是传说中错误率极高的二叉查找，大家必须小心谨慎 : : 不了解的同学可以Google/Baidu，或者参考数据结构与算法教程 : : 在bsearch的声明后进行实现，请仔细阅读函数说明，不要修改TEST CASE，贴出代码和运行结果 : : : : [QUOTE]#include<stdio.h> : : /** : * 函数功能描述: Binary Search : * 参数说明: int val 需要查询的数值 : * int* array 待查询数组,升序排列 : * int* steps 返回此次查询的循环次数,每次调用bsearch需将此变量重置为0 : * int* result_index 返回搜索结果的索引,没有查询到返回-1 : * 返回值: 异常情况返回-1 : * 没有找到结果返回0 : * 找到结果返回1 : */ : int bsearch(int val, int* array, int n, int* steps, int* result_index); : : : int main() { : int steps; : int result_index; : : printf("\nCASE_01:\n"); : int array1[] = {132, 222, 312, 423, 511, 612}; : bsearch(12, array1, sizeof(array1) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(24, array1, sizeof(array1) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(355, array1, sizeof(array1) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(4454, array1, sizeof(array1) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(533, array1, sizeof(array1) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(612, array1, sizeof(array1) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(-1, array1, sizeof(array1) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : : printf("\nCASE_02:\n"); : int array2[] = {-100, 2, 3, 1000, 1005, 1006}; : bsearch(1006, array2, sizeof(array2) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(-200, array2, sizeof(array2) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(3, array2, sizeof(array2) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : : printf("\nCASE_03:\n"); : int array3[] = {1, 2, 3, 4, 5, 6}; : bsearch(1, array3, sizeof(array3) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(2, array3, sizeof(array3) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(3, array3, sizeof(array3) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(4, array3, sizeof(array3) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(5, array3, sizeof(array3) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(6, array3, sizeof(array3) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(7, array3, sizeof(array3) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : : printf("\nCASE_04:\n"); : int array4[] = {-3, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; : bsearch(-1, array4, sizeof(array4) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(2, array4, sizeof(array4) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(-3, array4, sizeof(array4) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(4, array4, sizeof(array4) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(-5, array4, sizeof(array4) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(6, array4, sizeof(array4) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(-7, array4, sizeof(array4) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : : printf("\nCASE_05:\n"); : int *array5 = NULL; : bsearch(1006, array5, sizeof(array5) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : array5 = array4; : bsearch(-200, array5, 0, &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : bsearch(3, array5, sizeof(array5) / sizeof(int), &steps, &result_index); : printf("Steps: %d, Index: %d\n", steps, result_index); : : } : [/QUOTE] : -- : 珍惜生命与时光珍惜每一次快门 : : : ※ 修改:·coolfantasy 于 Jun 17 11:59:37 修改本文·[FROM: 220.181.38.*] : ※ 来源:·北邮人论坛 http://forum.byr.edu.cn·[FROM: 220.181.38.*]

coolfantasy机器人#8 · 2008/6/17

Bad Case Test 出错没关系但至少不能core掉这个case不会越界吧你说的那个例子越界了肯定不行【在 sunway 的大作中提到: 】 : int bsearch(int val, int* array, int n, int* steps, int* result_index) { : *steps=0; : *result_index=-1; : ...................

sunway机器人#9 · 2008/6/17

int *array5 = NULL; int a=10; int * ret=bsearch(&a,array5,1,4,fun); fun是一个简单的比较函数,这个例子用了stdlib下的bsearch,段错误【在 coolfantasy (Cool) 的大作中提到: 】 : Bad Case Test : 出错没关系但至少不能core掉 : 这个case不会越界吧你说的那个例子越界了肯定不行 : ...................

[坑] 大家来做题 之 二叉查找

[坑] 大家来做题之二叉查找