二分搜索算法实验报告.docx

二分搜索算法实验报告 实验一 二分搜索算法实验报告 一 实验目得 1、 理解分治算法得概念与基本要素; 2、 理解递归得概念; 3、 掌握设计有效算法得分治策略; 4、 通过二分搜索技术学习分治策略设计技巧; 二 二. 实验内容及要求 1. 使用二分搜索算法查找任意个有序数列中得指定元素。 2 通过上机实验进行算法实现。 . 保存与打印出程序得运行结果,并结合程序进行分析,上交实验报告。 4、 至少使用两种方法进行编程。 三 三. 实验原理 二分搜索算法也称为折半查找法，它充分利用了元素间得次序关系,采用分治策略,可在最坏得情况下用 O(lo n)完成搜索任务。 【基本思想】将个元素分成个数大致相同得两半,取 an与欲查找得 x 作比较,如果n/2则找到,算法终止。如果 xan/2,则我们只要在数组得左半部继续搜索 x（这里假设数组元素呈升序排列）。如果 xa/2,则我们只要在数组 a 得右半部继续搜索。 二分搜索法得应用极其广泛