用C#实现折半查找算法的可视化演示
时间：2022-10-11 06:22:31
摘要：折半查找算法用于在有序表中进行查找，是程序设计语言和数据结构课程中都需要掌握的一种查找算法，该文用c#编程，对这一算法的实现过程进行了动态演示，有助于初学者更好地理解和掌握这一算法的思想。
中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)29-7225-03
To Realize a Visual Demonstration of Binary Search Algorithm by C#
SUN Yi-xin
(Information Engineering Department of Weifang Engineering Vocational College, Qingzhou 262500, China)
Abstract: Binary search algorithm is used to search in ordered list. It is a searching algorithm which should be grasped when learning programming design languages and data structure. This paper presents a dynamic demonstration of the realization process of this algorithm by using C Programming, which is helpful for the beginners to better understand and grasp the idea of this algorithm.
Key words: binary search; ordered list; timer; the middle element
在日常生活中，人们几乎每天都要进行“查找”的工作。例如，查找某人的电话号码，查找某学生的考试成绩等等。在各种系统软件或应用软件中，查找也是最重要的一项功能。
所谓“查找”就是在一个含有众多的数据元素（或记录）的查找表中找到某个特定的“数据元素（或记录）”。若表中存在这样的一个记录，则称查找是成功的，可以给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，可以给出查找不成功的相应信息。
1 折半查找算法介绍
在计算机中进行查找的方法随数据结构的不同而不同。折半查找方法适用于查找存储在有序的线性表中的记录，其查找过程为：先确定待查记录所在的范围，然后以该范围内的中间记录的关键字和给定的关键字进行比较，若相等，则查找成功；若给定的关键字小于中间记录的关键字，则舍弃掉线性表的后半部分以缩小范围继续查找；若给定的关键字大于中间记录的关键字，则舍弃掉线性表的前半部分以缩小范围继续查找。循环直到新的区间位置记录的关键字等于给定值或者查找区间的大小小于零时（表明查找不成功）为止。
折半查找算法的描述如下：
算法：BinarySearch
输入：n个元素的升序数组A[1..n]和元素x。
输出：如果x=A[j]，1≤j≤n，则输出j，否则输出0。
low1；highn；j0
while (low≤high) and (j==0)
mid(low+high)/2
if x==A[mid] then jmid
else if x
else lowmid+1
end while
return j
2 用C#实现的动态演示程序
打开Visual Studio 2005，新建一个Visual C# Windows应用程序项目，项目名称为BinarySearch，将默认窗体名称Form1改为BinarySearchForm，在窗体上添加一个Panel控件，作为动态演示折半查找过程的平台，添加两个Timer控件，设置其Interval属性为1000，用来代替算法中的循环和查找比较过程，用Timer控件的定时特点来达到动态演示的效果。程序中的主要代码如下，为了有助于读者更好的理解，在其中添加了比较详细的注释：
private const int MAXNUMBERS = 10;//可以设置的最大数组容量为10
private int[] numbers=new int[MAXNUMBERS];//存放待处理的数据
//显示数据用的标签控件数组
private System.Windows.Forms.Label[] lblNumbers = new Label[MAXNUMBERS];
private System.Windows.Forms.Label lblData;
private int low; //记录搜索范围中第一个元素的位置
private int high;//记录搜索范围中最后一个元素的位置
private int mid; //记录搜索范围中中间元素的位置
private int searchData; //存放要查找的数据
//“生成数据”命令按钮，生成初始数据并安排界面
private void btnCreateNumber_Click(object sender, EventArgs e)
{ btnClear_Click(null, null);//清除面板中的标签
Random random = new Random();
searchData = random.Next(100);//随机产生待查找的数据
lblData = new Label();
lblData.Location = new Point(80, 20);
lblData.ForeColor = Color.Blue;
lblData.Text = searchData.ToString();
this.panNumber.Controls.Add(lblData);
for (int i = 0; i
{numbers[i] = random.Next(100);
}Array.Sort(numbers); //对数据序列进行排序
//将数据安排到界面上
for(int i=0;i< numbers.Length;i++)
{ lblNumbers[i] = new Label();
lblNumbers[i].Location = new Point(i * 60 + 80, 50);
lblNumbers[i].Size = new Size(50, 30);
lblNumbers[i].ForeColor = Color.Yellow;
lblNumbers[i].BackColor = Color.Red; ;
lblNumbers[i].Text = numbers[i].ToString();
lblNumbers[i].Font = new Font("宋体", 12);
lblNumbers[i].TextAlign = ContentAlignment.MiddleCenter;
this.panNumber.Controls.Add(lblNumbers[i]);
}}//开始查找按钮的单击事件
private void btnBeginSearch_Click(object sender, EventArgs e)
{btnBeginSearch.Enabled = false; //禁用查找按钮
low = 0; //设置查找范围的最小值的下标
high = MAXNUMBERS - 1; //设置查找范围的最大值的下标
//设置搜索范围的最小值和最大值的前景色和背景色以标识查找范围
lblNumbers[low].ForeColor = Color.Red;
lblNumbers[low].BackColor = Color.Yellow;
lblNumbers[high].ForeColor = Color.Red;
lblNumbers[high].BackColor = Color.Yellow;
tmrSearch.Enabled = true; //启动定时器以进行动态查找
}//控制排序的外层循环
private void tmrSearch_Tick(object sender, EventArgs e)
{ tmrSearch.Enabled = false;
if (low
{ //重新计算中间元素的下标，以便进行查找
mid = (low + high) / 2;
//设置中间元素的前景色和背景色
lblNumbers[mid].ForeColor = Color.White;
lblNumbers[mid].BackColor = Color.Blue;
tmrCompare.Enabled = true;//启动比较过程
}else if (low < numbers.Length && high >= 0)
{ //查找不到时的处理
lblNumbers[low].ForeColor = Color.Black;
lblNumbers[low].BackColor = SystemColors.Control;
lblNumbers[high].ForeColor = Color.Black;
lblNumbers[high].BackColor = SystemColors.Control;
tmrCompare.Enabled = false;
MessageBox.Show("未找到要查找的数据！", "数据未找到");
btnBeginSearch.Enabled = true;
} else
{ MessageBox.Show("未找到要查找的数据！", "数据未找到");
btnBeginSearch.Enabled = true;
}}
//进行比较和缩小查找范围的操作
private void tmrCompare_Tick(object sender, EventArgs e)
{ tmrCompare.Enabled = false;
if (searchData == numbers[mid])
{//查找到要找的数据
lblNumbers[low].ForeColor = Color.Black;
lblNumbers[low].BackColor = SystemColors.Control;
lblNumbers[high].ForeColor = Color.Black;
lblNumbers[high].BackColor = SystemColors.Control;
lblNumbers[mid].ForeColor = Color.White;
lblNumbers[mid].BackColor = Color.Blue;
string message = string.Format("要查找的数据在序列中的位置是{0}", mid);
MessageBox.Show(message, "找到数据");
btnBeginSearch.Enabled = true;
}else if (searchData < numbers[mid])
{ //通过颜色变换舍弃掉序列的后半部分
for (int m = mid; m
{ lblNumbers[m].ForeColor = Color.Black;
lblNumbers[m].BackColor = SystemColors.Control;
}high = mid - 1;
if (high >=low)
{ lblNumbers[high].ForeColor = Color.Red;
lblNumbers[high].BackColor = Color.Yellow;
}tmrSearch.Enabled = true;
} else
{ //通过颜色变换舍弃掉序列的前半部分
for (int m = low; m
{ lblNumbers[m].ForeColor = Color.Black;
lblNumbers[m].BackColor = SystemColors.Control;
}low = mid + 1;
if (low
{ lblNumbers[low].ForeColor = Color.Red;
lblNumbers[low].BackColor = Color.Yellow;
}tmrSearch.Enabled = true;
} }
3 程序运行界面效果
程序运行的界面效果如图1所示，从图中可以清楚地看到已经被舍弃掉的部分和还没查找完的部分，初始的数据以红色背景色和黄色前景色显示，查找范围的第一个和最后一个数据以黄色背景色和红色前景色标出，查找范围中的中间元素以蓝色背景色和白色前景色标出，舍弃掉的部分以系统背景色和黑色前景色显示。程序通过视觉变换和延时形成了动态演示查找过程的效果。如果运行时感到效果不理想，可以将数组容量设置的大一些，同时可以适当调整两个定时器的时间间隔，以控制查找的速度，从而可以更好的体会折半查找的过程。
4 结束语
算法一般是比较抽象的，我们在学习算法时，大多是通过老师根据一个具体的例子用粉笔在黑板上对算法的实现过程进行讲解，或通过教材上的描述进行自学，掌握起来非常不容易。在具体编程时一般只会看到算法实现的结果，而看不到算法的实现过程，缺乏直观性和生动性，学生难以接受。本文用C#编程对折半查找算法的实现过程进行了可视化的动态演示，有助于读者更好地掌握这一算法的基本思想，同时也希望能起到抛砖引玉的作用，大家共同开发一些算法的可视化演示程序，让初学者能够从中受益。
参考文献：
[1] 严蔚敏,吴伟民.数据结构（C语言版）[M].北京:清华大学出版社,1997.
[2] 王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2006.
[3] 李继武.Visual C#.NET项目开发实战[M].北京:清华大学出版社,2007.
[4] 林邦杰.深入浅出C#程序设计[M].北京:中国铁道出版社,2005.
