分治算法 |
您所在的位置:网站首页 › 二分检索的递归算法 › 分治算法 |
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 问题描述细节须知算法原理算法的思路算法的分析 问题描述给定已排好序的n个元素组成的数组,现要利用二分搜索算法判断特定元素x是否在该有序数组中 细节须知(1)由于可能需要对分治策略实现二分搜索的算法效率进行评估,故使用大量的随机数对算法进行实验(生成随机数的方法见前篇随笔)。 (2)由于二分搜索需要数据为有序的,故在进行搜索前利用函数库中sort函数对输入的数据进行排序。 (3)代码主要用到的是经典的二分查找加上递归。 (4)其中limit为所要从随机数文件中提取的数据的数量,以此为限来决定算法需要在多少个数据中进行搜索。 (5)为了使代码更人性化,加入了查找成功与失败的提醒,主要区别于Search函数中的返回值,若查找成功则返回1(满足1>0,即为查找成功),其余则返回0,即为查找失败。 (6)通过clock函数对算法运行的时间进行计算以评估算法效率。 算法原理假设搜索范围为数组a中的n个元素,要搜索的元素为x。 将n个元素分成个数大致相同的两半,取a[n/2]与x进行比较。如果x=a[n/2],则找到x,算法终止。如果xa[n/2],则只要在数组a的右半部继续搜索x。以此不断地将搜索范围折半,从而实现采用分治策略进行二分搜索。 代码实现: 1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define limit 100000 8 9 int Search(int R[],int low,int high,int k) //low表示当前查找的范围下界、high表示当前查找范围的上界,k为所要查找的内容 10 { 11 int mid; 12 13 if (lowk) //在R[low..mid-1]中递归查找 18 Search(R,low,mid-1,k); 19 else //在R[mid+1..high]中递归查找 20 Search(R,mid+1,high,k); 21 } 22 else 23 return 0; 24 } 25 26 int main(void) 27 { 28 ifstream fin; 29 int x; 30 int i; 31 int a[limit]; 32 int result; 33 34 fin.open("random_number.txt"); 35 if(!fin){ 36 cerr |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |