二分查找（Binary Search）

大家好，欢迎来到IT知识分享网。

二分查找（Binary Search）是一种高效的查找算法，适用于已排序的数组。它的基本思想是通过不断将查找范围缩小一半来快速定位目标值。

二分查找的原理

1. 前提条件：

• 数组必须是有序的（升序或降序）。

2. 算法步骤：

• 初始化两个指针：low 指向数组的起始位置，high 指向数组的末尾位置。
• 计算中间位置 mid = (low + high) / 2。
• 比较中间元素与目标值：
• 如果中间元素等于目标值，返回中间位置。
• 如果中间元素小于目标值，说明目标值在右半部分，更新 low = mid + 1。
• 如果中间元素大于目标值，说明目标值在左半部分，更新 high = mid – 1。
• 重复上述步骤，直到 low > high，表示目标值不存在。

3. 时间复杂度：

• O(log⁡n)，其中 nn 是数组的长度。

C语言实现二分查找

以下是二分查找的C语言实现代码：

#include 
  
    // 二分查找函数 int binarySearch(int arr[], int size, int target) { int low = 0; // 查找范围的起始位置 int high = size - 1; // 查找范围的结束位置 while (low <= high) { int mid = low + (high - low) / 2; // 计算中间位置 if (arr[mid] == target) { return mid; // 找到目标值，返回索引 } else if (arr[mid] < target) { low = mid + 1; // 目标值在右半部分 } else { high = mid - 1; // 目标值在左半部分 } } return -1; // 未找到目标值 } int main() { int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; // 已排序的数组 int size = sizeof(arr) / sizeof(arr[0]); // 数组长度 int target = 7; // 目标值 int result = binarySearch(arr, size, target); if (result != -1) { printf("目标值 %d 在数组中的索引是：%d\n", target, result); } else { printf("目标值 %d 未找到！\n", target); } return 0; } 
  

代码说明

1. binarySearch 函数：

参数：

• arr[]：已排序的数组。
• size：数组的长度。
• target：要查找的目标值。

返回值：

• 如果找到目标值，返回其索引。
• 如果未找到，返回 -1。

2. 主函数：

• 定义一个已排序的数组 arr。
• 调用 binarySearch 函数查找目标值。
• 根据返回值输出结果。

示例运行

输入：

int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; int target = 7;

输出：

目标值 7 在数组中的索引是：3

输入：

int target = 10;

输出：

目标值 10 未找到！

总结

• 二分查找是一种高效的查找算法，适用于已排序的数组。
• 时间复杂度为 O(log⁡n)，远优于线性查找的 O(n)。
• 实现时需要注意边界条件，例如 low 和 high 的更新。