c语言递归二分搜索法
你把
主()
{
"""""
C以递归方式实现二分搜索法C语言。 #包含stdio.h
int a[100]= {1，2，3，5，11，12，14，15，29，55 }；//数组中的数字(从小到大)
int k；//要查找的数字
int found(int x，int y)
{ int m = x(y-x)/2；
If(xy)//搜索后没有找到答案，返回-1。
return-1；
其他
{ if(a[m]==k)返回m；//如果找到，返回该位置。
else if(a[m]k) return found(x，m-1)；//向左看
else返回发现(m 1，y)；//向右看
}
}
int main()
{ scanf("%d "，k)；//输入要查找的数字。
printf("%d\n "，found(0，9))；//从数组a[0]到a[9]查找
返回0；
}
c语言二分法搜索排序问题 A.txt:读入数据
B.txt:写入排序数据
C.txt:编写搜索结果
#包含stdio.h
const int maxn = 1000
int num[maxn]，n；
void swap(int* x，int* y) {
* x ^= * y；
* y = *x^*y；
* x = *x^*y；
}
void finput() {
printf("-\ n从a.txt中读取数据\ n-\ n \ n ")；
FILE* fin = fopen("a.txt "，" r ")；
n = 0；
while ( fscanf(fin，" %d "，num[n])！= EOF ) {
n；
}
fclose(fin)；
}
空泡(){
printf("-\ n启动冒泡排序算法\ n ")；
for(int I = n-1；I 0；- i) {
for(int j = 0；j I；j) {
if (num[j] num[j 1]) {
swap(num[j]，num[j 1])；
}
}
}
printf("将排序的结果写入b . txt \ n-\ n \ n ")；
FILE* fout = fopen("b.txt "，" w ")；
for(int I = 0；I n；i) {
fprintf(fout，" %d\n "，num[I])；
}
fclose(fout)；
}
int rbesearch(int low，int high，int v) {
//递归二分搜索法
//返回v的索引，如果不存在，返回-1。
if(低==高){
if (num[low] == v)返回low；
return-1；
}
if (num[low] == v)返回low；
int mid =(低高)/2；
if (num[mid] v) {
return rbesearch(中1，高，v)；
}
否则{
return rbesearch(低、中、v)；
}
}
int nrb search(int low，int high，int v) {
//非递归二分搜索法
//返回v的索引，如果不存在，返回-1。
当(低高){
int mid =(低高)/2；
if (num[mid] v) {
低=中1；
}
否则{
高=中；
}
}
if (low == high num[low] == v) {
返低；
}
return-1；
}
无效搜索(){
printf("-\ n ")；
printf("开始搜索。\ n ")；
printf("结果将被写入c . txt \ n ")；
printf("请输入一个数字。如果num = -123456，退出。\ n ")；
FILE* file=fopen("c.txt "，" w ")；
while (true) {
int v；
scanf("%d "，v)；
if (v == -123456)破；
int rb = rbesearch(0，n-1，v)；
int nrb = nrbesearch(0，n-1，v)；
fprintf(file，" input: %d\n "，v)；
fprintf(file，“递归二分搜索法的结果:%d\n”，Rb)；
fprintf(file，“非递归二分搜索法的结果:%d\n\n”，nrb)；
printf("递归二分搜索法的结果:%d\n "，Rb)；
printf("非递归二分搜索法的结果:%d\n\n "，nrb)；
}
fclose(文件)；
}
int main() {
finput()；
泡泡()；
search()；
返回0；
}
用递归方法写出有序数组的二分搜索法算法 什么是二分搜索法？
二分搜索法，也称为二分搜索法，是一种有效的搜索方法。但是二分搜索法要求线性表必须采用顺序存储结构，表中的元素按关键字顺序排列。
二分搜索法的优势和劣势
优点是比较次数少，搜索速度快，平均性能好；
它的缺点是要查找的列表要求是有序的，而且很难插入和删除。
因此，对半查找的方法适用于查找不频繁变化的频繁有序列表。
使用条件:搜索序列是序列结构，有序。
过程
首先，假设表格中的元素按升序排列，将记录在表格中间的关键词与搜索关键词进行比较，如果相等，则搜索成功；否则，使用中间位置记录将表分成两个子表。如果中间位置记录的关键字大于搜索关键字，则进一步搜索前面的子表，否则进一步搜索后面的子表。重复上述过程，直到找到满足条件的记录使搜索成功，或者直到子表不存在，此时搜索不成功。
利用循环实现二分法搜索
公共类二进制搜索{
公共静态void main(String[] args) {
//生成随机数组int[]array = suiji()；
//对数组进行排序。排序(数组)；
System.out.println("生成的随机数组为:" arrays . tostring(array))；
System.out.println("要查找的值:")；
扫描仪输入=新扫描仪(system . in)；
//搜索的目标值int aim = input . nextint()；
//用二分法求int index =二分搜索法(array，aim)；
System.out.println("被搜索值的索引位置:" index ")；
}
/* * *生成随机数组*
* @return返回值，返回随机数组*/
private static int[] suiji() {
// random.nextInt(n) m返回随机数int n = new Random()。m和m ^ n-1之间的nextInt(6)5；
int[]array = new int[n]；
//循环遍历为数组赋值(int I = 0；I数组.长度；i ) {
array[i] = new Random()。nextInt(100)；
}
返回数组；
}
/* * *二分法搜索-循环实现*
* @ Paraarray查找数组* @ Paraaim查找值* @return返回值，成功返回索引和-1 */
private static int binary search(int[]array，int aim) {
//数组int left的最小索引值= 0；
//数组int right的最大索引值= array . length-1；
int mid
while (left = right) {
mid =(左右)/2；
//如果搜索值小于中间值，则将整个搜索范围的前半部分作为新的搜索范围if (aim array[mid]) {
右=中1；
//如果搜索值大于中间值，则将整个搜索范围的后一半作为新的搜索范围} else if (aim array[mid]) {
左=中1；
//如果搜索数据正好等于中间元素值，则放回中间元素值的索引} else {
返回mid
}
}
return-1；
}}
操作结果演示:
从上面的运行结果我们知道，如果要查找的数据存在于数组中，则输出数组中数据的索引；如果不存在，输出-1，即print -1，数组中不存在该数，否则存在。
第四，二分搜索法是通过递归实现的。
公共类BinarySearch2 {
公共静态void main(String[] args) {
//生成随机数组int[]array = suiji()；
//对数组进行排序。排序(数组)；
System.out.println("生成的随机数组为:" arrays . tostring(array))；
System.out.println("要查找的值:")；
扫描仪输入=新扫描仪(system . in)；
//搜索的目标值int aim = input . nextint()；
//用二分法求int index =二分搜索法(array，aim，0，array。长度-1)；
System.out.println("被搜索值的索引位置:" index ")；
}
/* * *生成随机数组* * @返回返回值，返回随机数组*/
private static int[] suiji() {
// Random.nextInt(n) m返回随机数int n = new Random()。m和m ^ n-1之间的nextInt(6)5；
int[]array = new int[n]；
//循环遍历为数组赋值(int I = 0；I数组.长度；i ) {
array[i] = new Random()。nextInt(100)；
}
返回数组；
}
/* * *二分法搜索-递归方式* * @ Paraarray查找数组* @ Paraaim查找值* @ Paraleft左最小值* @ Pararight右最大值* @返回返回值，索引返回成功，-1 */
private static int binary search(int[]array，int aim，int left，int right) {
if (aim数组[左] || aim数组[右]) {
return-1；
}
//求中间值int mid =(左右)/2；
if (array[mid] == aim) {
返回mid
} else if (array[mid] aim) {
//如果中间值大于要求的值，继续从左半部分递归返回二分搜索法(array，aim，left，mid-1)；
}否则{
//如果中间值小于要查找的值，继续递归返回二分搜索法(array，aim，mid 1，array。长度-1)从右半部开始；
}
}}
操作结果演示:
总结:
与循环相比，递归的代码更简单，但它消耗更多的时间和空间，效率很低。在实际学习和工作中，根据情况选择使用。通常如果我们用loop来实现代码，只要不是太繁琐，就选择loop来实现~
如何用C语言的递归函数实现二分搜索法算法 半搜索法又称二分搜索法法，充分利用元素之间的顺序关系，采用分治策略，在最坏的情况下可以用O(log n)完成搜索任务。它的基本思想是知道一个有n个元素的有序序列，将n个元素分成数目大致相同的两半，将a[n/2]与待求的X进行比较，如果x=a[n/2]，则求X，算法终止。如果xa[n/2]，那么我们只需要在数组A的左半部分继续搜索x(假设这里数组元素按升序排列)。如果xa[n/2]，那么我们只需要继续在数组A的右半部分搜索X，直到找到X或者找不到！
如果是常规方法，那么我们可以循环上面的算法。如果找到了，就退出循环，否则继续循环，直到左下标位置小于等于右下标位置。
按照你哥的意思是用递归的方法来搜索，那么很可能就是上面的算法，只不过循环法改为递归法:如果没有找到，就确定一个新的搜索范围，也就是下标左右位置，然后把新的参数传给函数继续调用函数进行递归搜索！！
递归实现的详细代码如下:
#包含stdio.h
#定义数组_大小10
#define NOT_FOUND -1
int BinarySearch(int array[]，int left，int right，int NumToSearch)
{
int mid =(左右)/2；
if(左=右)
{
if (NumToSearch == array[mid])
{
返回mid
}
else if (NumToSearch数组[mid])
{
右=中1；
返回BinarySearch(array，left，right，NumToSearch)；
}
其他
{
左=中1；
返回BinarySearch(array，left，right，NumToSearch)；
}
}
返回NOT _ FOUND
}
int main()
{
int a[ARRAY_SIZE] = {2，5，6，7，13，20，22，27，112，222 }；//假设一个已知的有序升序序列。
int result = 0；//搜索的结果
int x = 13//假设我们要找的数字是13。
int left = 0；//序列开始下标
int right = ARRAY _ SIZE-1；//序列结束下标
result = BinarySearch(a，left，right，x)；
if (result == NOT_FOUND)
{
printf("未找到！\ n ")；
}
其他
{
printf("在数组a中找到%d，是一个[%d]\n "，x，result)；
}
返回0；
}
希望对你有帮助，兄弟！
最后更新于 2023-10-11 10:51:03 并被添加「」标签，已有 位童鞋阅读过。
本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处
相关文章