C语言中如何实现并应用折半查找算法？

本文共计928个文字，预计阅读时间需要4分钟。

目录

1.折半查找介绍

1.1 定义 1.2 基本原理 1.3 时间复杂度与空间复杂度 1.4 优缺点

2.代码实现

2.1 代码设计 2.2 代码实现

目录

• 1. 折半查找介绍
• 1.1 定义
• 1.2 基本原理
• 1.3 时间复杂度与空间复杂度
• 1.4 优缺点
• 2. 代码实现
• 2.1 代码设计
• 2.2 代码实现

1. 折半查找介绍

1.1 定义

折半查找也称二分查找，是一种在有序数组中查找某一特定元素的搜索算法，每一次查找，搜索范围均缩小一半，效率较高。如果数组是乱序状态，则应排序，再进行查找。

1.2 基本原理

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半 。