C语言之二分查找

目录

一 简介

二 代码实现

三 时空复杂度

A.时间复杂度(Time Complexity):

B.空间复杂度(Space Complexity):

C.总结


一 简介

二分查找算法(Binary Search)在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) { // 如果中间元素就是目标值
            return mid; // 返回目标值所在的位置
        } else if (arr[mid] < target) { // 如果中间元素小于目标值
            left = mid + 1; // 在右半部分(包括中间点右侧)进行查找
        } else { // 若中间元素大于目标值
            right = mid - 1; // 在左半部分(包括中间点左侧)进行查找
        }
    }

    // 若未找到目标值,则返回-1表示目标值不在数组中
    return -1;
}

int main() {
    int sortedArray[] = {1, 3, 5, 7, 9, 11, 13, 15};
    int n = sizeof(sortedArray) / sizeof(sortedArray[0]);
    int target = 7;

    int result = binarySearch(sortedArray, 0, n - 1, target);

    if (result != -1) {
        printf("Element %d is present at index %d.\n", target, result);
    } else {
        printf("Element %d is not found in the array.\n", target);
    }

    return 0;
}

在这段代码中:

  • binarySearch 函数接受一个已排序的整数数组、左边界索引、右边界索引以及要查找的目标值。
  • 它首先计算数组中间位置的索引,并与目标值比较。
  • 如果目标值等于中间元素,那么就找到了目标并返回其索引。
  • 如果目标值小于中间元素,说明目标值应该位于中间元素的左边,因此更新右边界为“中间索引 - 1”。
  • 否则,目标值应该位于中间元素的右边,所以更新左边界为“中间索引 + 1”。
  • 这个过程会一直重复,直到找到目标值或者左右边界交叉,此时表明目标值不在数组中。

三 时空复杂度

二分查找算法(Binary Search)是一种在有序数组中查找特定元素的高效算法。其时空复杂度如下:

A.时间复杂度(Time Complexity):

  • 平均情况最好情况下,二分查找的时间复杂度都是 O(log n),其中 n 为数组中的元素个数。这是因为每次迭代都将搜索区间减半,直到找到目标值或搜索区间为空。

最坏情况下,如果要查找的元素不在数组中,那么同样需要进行 log n 次比较才能确定这一点,所以即使在最坏情况下,时间复杂度仍然是 O(log n)。

B.空间复杂度(Space Complexity):

  • 二分查找的空间复杂度是 O(1) 或常数空间复杂度。这是因为算法在执行过程中仅使用了几个固定大小的变量,如存储中间索引、左边界和右边界的变量,并未依赖于输入数据规模大小的数据结构。无论输入数组多大,辅助空间的需求保持不变。

C.总结

总结来说,二分查找算法具有非常优秀的效率,在处理大规模有序数据时尤为适用,它能够在相对较短的时间内完成查找任务,且占用的空间资源极小。