二分法在 C 语言中的实现 (二分法在c语言中的应用)

文章编号：808 / 更新时间：2024-12-30 04:06:49 / 浏览：次
二分法在

简介

二分法是一种在有序数组中快速查找特定元素的算法。它通过将数组分成两半来工作，并不断缩小搜索范围，直到找到元素或确定它不存在。二分法的时间复杂度为 O(logn)，其中 n 是数组的长度。与其他搜索算法（如线性搜索）相比，它的效率要高得多，特别是对于大型数组。

二分法算法

以下是二分法的 C 语言实现：```cint binary_search(int arr[], int n, int x) {int low = 0, high = n - 1;while (low <= high) {int mid = (low + high) / 2;if (arr[mid] == x) {return mid; } else if (arr[mid] < x) {low = mid + 1;} else {high = mid - 1;}}return -1;}```

算法步骤

1. 初始化两个索引 low 和 high，分别指向数组的第一个和最后一个元素。2. 重复以下步骤，直到 low 大于 high：- 计算数组中间的索引 mid。- 如果 arr[mid] 等于 x，则返回 mid。- 如果 arr[mid] 小于 x，则将 low 设置为 mid + 1。- 如果 arr[mid] 大于 x，则将 high 设置为 mid - 1。3. 如果算法没有返回任何索引，则表示 x 不在数组中，返回 -1。

示例

考虑以下有序数组：```arr = [1, 3, 5, 7, 9, 11, 13, 15]```查找元素 7：1. 初始化 low = 0，high =7。2. mid = (0 + 7) / 2 = 3。3. arr[mid] = 7，即等于 x。4. 返回 mid = 3。查找元素 10：1. 初始化 low = 0，high = 7。2. mid = (0 + 7) / 2 = 3。3. arr[mid] = 7，即小于 x。4. 更新 low = 4。5. 重复步骤 2-4，直到 low 大于 high。6. 返回 -1，表示 10 不在数组中。