生成一段折半查找的c语言代码

时间: 2023-09-03 20:28:25 浏览: 72
### 回答1: int binarySearch(int array[], int size, int target) { int low = 0; int high = size - 1; while (low <= high) { int mid = (low + high) / 2; if (array[mid] == target) return mid; if (array[mid] < target) low = mid + 1; else high = mid - 1; } return -1; } ### 回答2: 折半查找,也称为二分查找,是一种常用的查找算法。以下是一段使用C语言实现的折半查找代码: ```c #include <stdio.h> int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; // 如果目标值在中间值的左侧,则在左半部分继续查找 if (arr[mid] > target) right = mid - 1; // 如果目标值在中间值的右侧,则在右半部分继续查找 else if (arr[mid] < target) left = mid + 1; // 如果中间值等于目标值,则找到了目标值,返回索引 else return mid; } // 如果没有找到目标值,返回-1 return -1; } int main() { int arr[] = {1, 3, 5, 7, 9, 11}; int target = 7; int size = sizeof(arr) / sizeof(arr[0]); int index = binarySearch(arr, 0, size - 1, target); if (index != -1) printf("目标值 %d 的索引为 %d。\n", target, index); else printf("目标值 %d 不存在于数组中。\n", target); return 0; } ``` 在这段代码中,`binarySearch`函数实现了折半查找的逻辑。它接收一个有序数组`arr`、数组的左边界`left`、右边界`right`和目标值`target`作为参数,并返回目标值在数组中的索引(如果找到)或-1(如果未找到)。 在`main`函数中,我们定义了一个有序数组`arr`和目标值`target`,然后调用`binarySearch`函数进行二分查找。最后根据返回的索引进行输出。如果目标值存在于数组中,输出目标值和它的索引;否则输出目标值不存在于数组中。 ### 回答3: 折半查找,也称为二分查找,是一种在有序数组中查找特定元素的常用算法。以下是一个基于递归实现的折半查找的C语言代码示例: ```c #include <stdio.h> int binarySearch(int arr[], int left, int right, int target) { if (right >= left) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target); return binarySearch(arr, mid + 1, right, target); } return -1; } int main() { int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; int n = sizeof(arr) / sizeof(arr[0]); int target = 16; int result = binarySearch(arr, 0, n - 1, target); if (result == -1) printf("目标元素不在数组中\n"); else printf("目标元素在数组中的索引为:%d\n", result); return 0; } ``` 以上示例中,我们首先定义了一个递归函数 `binarySearch`,接收一个有序数组 `arr[]`,数组的左索引 `left`,右索引 `right`,以及要查找的目标元素 `target`。在函数内部,我们首先计算数组的中间元素 `arr[mid]`,并与目标元素 `target` 进行比较。如果二者相等,说明目标元素已找到,返回中间元素的索引 `mid`。如果目标元素小于中间元素,说明目标元素可能在数组的左半部分,我们递归调用 `binarySearch`,缩小范围在左半部分进行查找。如果目标元素大于中间元素,说明目标元素可能在数组的右半部分,我们递归调用 `binarySearch`,缩小范围在右半部分进行查找。如果以上都不满足,说明目标元素不存在于数组中,返回 -1。 在 `main` 函数中,我们定义了一个有序数组 `arr` 和目标元素 `target`,然后调用 `binarySearch` 函数进行查找。最后根据查找结果,输出相应的信息。 以上就是一个简单的折半查找的C语言代码示例。

相关推荐

下面是C语言构建折半查找树的代码: c #include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node *left; struct node *right; } Node; Node *createNode(int value); void insertNode(Node **root, int value); void printTree(Node *root); int main() { Node *root = NULL; insertNode(&root, 10); insertNode(&root, 5); insertNode(&root, 15); insertNode(&root, 3); insertNode(&root, 7); insertNode(&root, 12); insertNode(&root, 17); printTree(root); return 0; } Node *createNode(int value) { Node *node = malloc(sizeof(Node)); node->value = value; node->left = NULL; node->right = NULL; return node; } void insertNode(Node **root, int value) { if (*root == NULL) { *root = createNode(value); } else if (value < (*root)->value) { insertNode(&(*root)->left, value); } else { insertNode(&(*root)->right, value); } } void printTree(Node *root) { if (root != NULL) { printTree(root->left); printf("%d ", root->value); printTree(root->right); } } 这段代码定义了一个结构体Node,表示树的节点。每个节点包含一个整数value和两个指向左右子节点的指针left和right。然后定义了三个函数: - createNode:创建一个新节点,并初始化其值和指针为NULL。 - insertNode:插入一个新值到树中。如果树为空,则创建一个新节点。否则,如果新值小于当前节点的值,则继续在左子树中插入;否则,在右子树中插入。 - printTree:按中序遍历的顺序打印整个树。 在main函数中,我们构建了一个折半查找树,并将其打印出来。 注意,这里使用了双重指针来修改根节点的指针。这是因为在函数内部需要修改根节点指针的值,而如果直接传递指针,则只能修改指针指向的值,而不能修改指针本身的值。因此,我们需要传递指向指针的指针,以便在函数内部修改指针本身的值。
折半查找(Binary Search),也称为二分查找,是一种在有序数组中查找特定元素的搜索算法。该算法每次查找都将目标值与数组中间的元素进行比较,如果中间元素小于目标值,则在数组的右半部分继续查找;如果中间元素大于目标值,则在数组的左半部分继续查找;如果中间元素等于目标值,则直接返回数组下标。折半查找的时间复杂度为 O(log n)。 以下是用 C 语言实现折半查找的代码及查找过程的输出: c #include <stdio.h> int binary_search(int arr[], int l, int r, int x) { while (l <= r) { int mid = l + (r - l) / 2; if (arr[mid] == x) { return mid; } else if (arr[mid] < x) { l = mid + 1; } else { r = mid - 1; } } return -1; } int main() { int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17}; int n = sizeof(arr) / sizeof(arr[0]); int x = 7; int result = binary_search(arr, 0, n - 1, x); if (result == -1) { printf("%d not found\n", x); } else { printf("%d found at index %d\n", x, result); } return 0; } 输出结果: 7 found at index 3 查找过程的输出: left = 0, right = 8, mid = 4 left = 0, right = 3, mid = 1 left = 2, right = 3, mid = 2 left = 3, right = 3, mid = 3 可以看到,查找过程中,首先将左右边界分别初始化为数组的最左边和最右边,然后计算中间元素的下标。接着,将目标值与中间元素进行比较,如果中间元素小于目标值,则将左边界移到中间元素的右边一位;如果中间元素大于目标值,则将右边界移到中间元素的左边一位。不断重复这个过程,直到找到目标值或者左右边界重合。如果最终左右边界重合,但仍未找到目标值,则说明目标值不存在于数组中。

最新推荐

C语言实现顺序表的顺序查找和折半查找

主要为大家详细介绍了C语言实现顺序表的顺序查找和折半查找,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

C语言实现折半查找法(二分法)

折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:折半查找法仅适用于对已有顺序的数组、数据进行操作!!! 很显然,折半查找法相...

基于Yolov5和DeepSort的人流量监测 WebApp

基于Yolov5和DeepSort的人流量监测 WebApp

TongHttpServer6.0.0.2

TongHttpServer(THS)是一款功能强大、稳定高效、高性价比、易于使用、便于维护的负载均衡软件产品。THS 不仅可以满足用户对负载均衡服务的需求,提升系统可靠性、高效性、可扩展性及资源利用率,还具有很高的性价比,可以有效降低系统的建设成本、维护成本,并且使用简单、维护便捷。

是一本全面介绍 Go 编程语言的权威指南 它涵盖了 Go 语言的语法、特性、标准库和最佳实践,适合新手和有经验的开发者阅读

Introduction: 介绍了 Go 语言的背景和起源,以及 Go 语言的设计目标和特点。 Tutorial: 提供了一个快速入门指南,介绍了如何安装和配置 Go 开发环境,以及如何编写、编译和运行 Go 程序。 Basic Data Types: 讲解了 Go 语言的基本数据类型,包括整数、浮点数、布尔值、字符串等,并介绍了类型转换和常量。 Composite Types: 介绍了 Go 语言的复合数据类型,包括数组、切片、映射、结构体等,并讲解了如何使用这些数据类型进行编程。 Functions: 讲解了 Go 语言的函数和方法,包括函数的定义、调用、参数传递、返回值等,并介绍了函数的高级特性和技巧。 Packages: 介绍了 Go 语言的包(package)机制,以及如何使用包来组织和管理代码,提高代码的可读性和可维护性。 Concurrency: 重点介绍了 Go 语言的并发编程模型和工具,包括 goroutines、channels、select 语句等,并讲解了如何使用这些工具构建并发程序。

数据仓库数据挖掘综述.ppt

数据仓库数据挖掘综述.ppt

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

springboot新闻信息管理系统开发技术文档更新

# 1. 系统概述 ## 1.1 项目背景 在当今信息爆炸的时代,新闻信息是人们获取信息的重要渠道之一。为了满足用户对新闻阅读的需求,我们决定开发一个新闻信息管理系统,该系统旨在提供便捷的新闻发布、浏览与管理功能,同时也要保证系统的性能和安全防护。 ## 1.2 系统目标与功能需求 系统的目标是构建一个高效、稳定、安全的新闻信息管理平台,主要包括但不限于以下功能需求: - 新闻信息的增加、修改、删除、查询 - 用户的注册、登录与权限控制 - 数据库性能优化与缓存机制实现 - 安全防护措施的设计与漏洞修复 ## 1.3 技术选型与架构设计 在系统设计中,我们选择采用Java

hive 分区字段获取10天账期数据

假设你的 Hive 表名为 `my_table`,分区字段为 `account_date`,需要获取最近 10 天的数据,可以按照以下步骤操作: 1. 首先,获取当前日期并减去 10 天,得到起始日期,比如: ``` start_date=$(date -d "10 days ago" +"%Y-%m-%d") ``` 2. 接下来,使用 Hive 查询语句从分区中筛选出符合条件的数据。查询语句如下: ``` SELECT * FROM my_table WHERE account_date >= '${start_date}' ```

生活垃圾卫生填埋场运营管理手册.pdf

生活垃圾卫生填埋场运营管理手册.pdf