积分商城

最新搜索： stm32 jflash 人形机器人 CRC32校验工具 STC8H8K64S4U
您现在的位置是：首页 > 技术资料 > 用二分查找求解有序数组中查找目标值的过程
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

用二分查找求解有序数组中查找目标值的过程

更新时间：2026-10-17 12:18:56 大小：38K 上传用户：潇潇江南查看TA发布的资源 标签：二分查找有序数组目标值查找C语言实现迭代算法 下载积分：2分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

用二分查找求解有序数组中查找目标值的过程 问题定义 给定一个升序排列的整数数组和一个目标值，要求在数组中查找该目标值是否存在，若存在返回其索引，否则返回 -1。 例如数组 ，查找目标值 9，其索引为 4。 二分查找的核心思想 二分查找利用数组有序的特性，每次将搜索范围缩小一半。通过比较中间元素与目标值，可以确定目标值在左半还是右半部分： 取当前区间的中间位置 mid。 若 a[mid] == target，找到目标，返回 mid。 若 a[mid] > target，说明目标在左半部分，收缩右边界。 若 a[mid] < target，说明目标在右半部分，收缩左边界。 重复直到区间为空。 每轮搜索范围减半，因此 个元素只需约 次比较。 C 代码实现（迭代） c#include

int binarySearch(int *a, int n, int target) { int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // 防止溢出 if (a[mid] == target) return mid; else if (a[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1;}int main() { int a[] = {-1, 0, 3, 5, 9, 12}; int n = 6; printf("%d\n", binarySearch(a, n, 9)); printf("%d\n", binarySearch(a, n, 2)); return 0;} 运行结果分别为 4 和 -1，符合预期。 边界与细节处理 循环条件 lo <= hi="" lo=""> hi 时区间为空，说明未找到。 mid = lo + (hi - lo) / 2 的写法可避免 (lo + hi) 可能溢出。 二分查找的前提是数组必须有序，否则结果无意义。 复杂度分析 时间复杂度：每轮减半，。 空间复杂度：迭代实现只需常数空间，。 扩展：查找边界 二分查找还可用于查找"第一个不小于目标值的位置"或"最后一个不大于目标值的位置"（lower_bound / upper_bound），只需调整收缩方向即可。这些变体广泛用于有序数据的区间查询。 应用场景 二分查找是最基础的算法之一，广泛用于： 有序数组的高效查找。 单调函数求零点或极值。 各种"二分答案"问题的底层支撑。 二分查找每次将搜索范围减半，在 O(log N) 时间内完成有序数组的目标值查找。

部分文件列表

文件名 大小
用二分查找求解有序数组中查找目标值的过程.docx 38K

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号