《对分查找及其算法实现》教学设计

《对分查找及其算法实现》教学设计（精选2篇）

1.《对分查找及其算法实现》教学设计 篇一

算法设计思想如下：

(1)设置初始区间，low=1;high=length，

(2)当low>high时，返回查找失败信息。

(3)取中点，low<=high，mid=(low+high)/2。

a.若kx

b.若kx>a[mid],查找改在右半区进行，low=mid+1;转向步骤(2)。

c.若ax=a[mid]，查找成功，返回数据位置。

代码实现：

#include int b_search(int x, int a[], int n) //折半查找函数{ int low = 0; int high = n ; if (low > high) { return -1; } else { while (low <= high) {int mid = (low + high) / 2;if (a[mid] < x){ low = mid + 1;}else if (a[mid] > x){ high = mid - 1;}else{ return mid;} } } return -1;}int main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int key = 0; int sz = sizeof(arr) / sizeof(arr[0]); scanf(“%d”, &key); int ret = b_search(key, arr, sz); if (ret == -1) { printf(“不存在这个数!n”); } else { printf(“%dn”, ret); } return 0;}

2.《对分查找及其算法实现》教学设计 篇二

所谓“查找”就是在一个含有众多的数据元素(或记录)的查找表中找到某个特定的“数据元素(或记录)”。若表中存在这样的一个记录,则称查找是成功的,可以给出整个记录的信息,或指示该记录在查找表中的位置;若表中不存在关键字等于给定值的记录,则称查找不成功,可以给出查找不成功的相应信息。

1 折半查找算法介绍

在计算机中进行查找的方法随数据结构的不同而不同。折半查找方法适用于查找存储在有序的线性表中的记录,其查找过程为:先确定待查记录所在的范围,然后以该范围内的中间记录的关键字和给定的关键字进行比较,若相等,则查找成功;若给定的关键字小于中间记录的关键字,则舍弃掉线性表的后半部分以缩小范围继续查找;若给定的关键字大于中间记录的关键字,则舍弃掉线性表的前半部分以缩小范围继续查找。循环直到新的区间位置记录的关键字等于给定值或者查找区间的大小小于零时(表明查找不成功)为止。

折半查找算法的描述如下:

2 用C#实现的动态演示程序

打开Visual Studio 2005,新建一个Visual C#Windows应用程序项目,项目名称为Binary Search,将默认窗体名称Form1改为Binary Search Form,在窗体上添加一个Panel控件,作为动态演示折半查找过程的平台,添加两个Timer控件,设置其Interval属性为1000,用来代替算法中的循环和查找比较过程,用Timer控件的定时特点来达到动态演示的效果。程序中的主要代码如下,为了有助于读者更好的理解,在其中添加了比较详细的注释:

3 程序运行界面效果

程序运行的界面效果如图1所示,从图中可以清楚地看到已经被舍弃掉的部分和还没查找完的部分,初始的数据以红色背景色和黄色前景色显示,查找范围的第一个和最后一个数据以黄色背景色和红色前景色标出,查找范围中的中间元素以蓝色背景色和白色前景色标出,舍弃掉的部分以系统背景色和黑色前景色显示。程序通过视觉变换和延时形成了动态演示查找过程的效果。如果运行时感到效果不理想,可以将数组容量设置的大一些,同时可以适当调整两个定时器的时间间隔,以控制查找的速度,从而可以更好的体会折半查找的过程。

4 结束语

算法一般是比较抽象的,我们在学习算法时,大多是通过老师根据一个具体的例子用粉笔在黑板上对算法的实现过程进行讲解,或通过教材上的描述进行自学,掌握起来非常不容易。在具体编程时一般只会看到算法实现的结果,而看不到算法的实现过程,缺乏直观性和生动性,学生难以接受。本文用C#编程对折半查找算法的实现过程进行了可视化的动态演示,有助于读者更好地掌握这一算法的基本思想,同时也希望能起到抛砖引玉的作用,大家共同开发一些算法的可视化演示程序,让初学者能够从中受益。

参考文献

[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.

[2]王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2006.

[3]李继武.Visual C#.NET项目开发实战[M].北京:清华大学出版社,2007.