课 程 设 计 说 明 书 设计题目： 二分查找程序的实现 专业： 班级： 设计人： 山 东 科 技 大 学 年 月 日 课 程 设 计 任 务 书 学院：信息科学与工程学院 专业： 班级： 姓名： 一、课程设计题目： 二分查找程序的实现 二、课程设计主要参考资料 （1 ） 计算机算法设计与分析（第三版）王晓东著 （2 ） 三、课程设计应解决的主要问题 （1 ） 二分查找程序的实现 （2 ） （3 ） 四、课程设计相关附件（如：图纸、软件等）： （1 ） （2 ） 五、任务发出日期： 2 0 1 3 -1 1 -2 1 课程设计完成日期： 2 0 1 3 -1 1 -2 4 指导教师签字： 系主任签字 ： 指导教师对课程设计的评语 成绩： 指导教师签字： 年 月 日 二分查找程序的实现 一、 设计目的 算法设计与分析是计算机科学与技术专业的软件方向的必修课。同时，算法设计与分析既有较强的理论性，也有较强的实践性。算法设计与分析的实验过程需要完成课程学习过程各种算法的设计和实现，以达到提高教学效果，增强学生实践动手能力的目标。 用分治法，设计解决二分查找程序的实现问题的一个简捷的算法。通过解决二分查找程序的实现问题，初步学习分治策略。 二、 设计要求 给定已按升序排好序的n 个元素 a[0:n-1]，现要在这 n 个元素中找出一特定元素 x。实现二分搜索的递归程序并进行跟踪分析其执行过程。 用顺序搜索方法时，逐个比较 a[0:n-1]中的元素，直至找出元素 x，或搜索遍整个数组后确定 x 不在其中。这个方法没有很好的利用 n 个元素已排好序这个条件，因此在最坏情况下，顺序搜索方法需要 O(n )次比较。要求二分法的时间复杂度小于 O(n )。 三、 设计说明 （一）、需求分析 二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用 O(lo gn )时间完成搜索任务。 该算法的流程图如下： 开始bott=0,top=n-1bott<=topYmid=(bott+top)/2x ==a[mid]Nx
a[n/2]，则只要在数组 a 的右半部分继续搜索 x 。 由于二分查找的数组不一定是一个整数数组，所以我采用了 C++中的模板函数，...
