分治算法

您所在的位置：网站首页 › 二分检索的递归算法 › 分治算法

分治算法

2024-07-07 16:05| 来源: 网络整理| 查看: 265

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录问题描述细节须知算法原理算法的思路算法的分析

问题描述

给定已排好序的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

【本文地址】

分治算法

分治算法

今日新闻

推荐新闻