引言

在計算機科學領域，查找是一項基本操作，而二分查找是一種高效的查找算法。本博客將詳細解釋一個簡單的C語言程序，演示如何使用標準庫函數qsort和bsearch來對一個整數數組進行排序和二分查找。

代碼解析

包含頭文件

#include <stdio.h>
#include <stdlib.h>

首先，我們包含了兩個標準頭文件，stdio.h用于輸入輸出操作，stdlib.h用于內存分配和其他一些雜項功能。

比較函數

int compareIntegers(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}

定義了一個比較函數compareIntegers，該函數用于在排序和二分查找時比較兩個整數。這個函數的作用是返回a - b的值，即升序排序。

主函數

int main() {// 創建已排序的整數數組int numbers[] = {101, 305, 248, 407, 109};int numNumbers = sizeof(numbers) / sizeof(numbers[0]);// 排序數組qsort(numbers, numNumbers, sizeof(numbers[0]), compareIntegers);// 設置要查找的 numberint targetNumber = 305;// 使用bsearch搜索學生int *result = (int *)bsearch(&targetNumber, numbers, numNumbers, sizeof(numbers[0]), compareIntegers);// 檢查結果并輸出if (result != NULL) {printf("Number found: %d\n", *result);} else {printf("Number %d not found\n", targetNumber);}return 0;
}

創建并排序數組

int numbers[] = {101, 305, 248, 407, 109};
int numNumbers = sizeof(numbers) / sizeof(numbers[0]);
qsort(numbers, numNumbers, sizeof(numbers[0]), compareIntegers);

在主函數中，我們首先創建了一個整數數組numbers，然后使用sizeof操作符計算數組元素個數。接下來，我們使用qsort函數對數組進行升序排序，傳遞了比較函數compareIntegers來定義排序順序。

二分查找

int targetNumber = 305;
int *result = (int *)bsearch(&targetNumber, numbers, numNumbers, sizeof(numbers[0]), compareIntegers);

設置要查找的目標數字為305，然后使用bsearch函數在已排序的數組中進行二分查找。同樣，我們傳遞了比較函數compareIntegers來確保查找的一致性。

輸出結果

if (result != NULL) {printf("Number found: %d\n", *result);
} else {printf("Number %d not found\n", targetNumber);
}

最后，我們檢查bsearch的結果。如果找到了目標數字，就輸出找到的數字；否則，輸出未找到的消息。

時間復雜度

讓我們分析一下這個程序中排序和查找部分的時間復雜度：

1. 排序 (qsort)：

   • 時間復雜度：O(n * log(n))
     • qsort通常使用快速排序算法，其平均時間復雜度為O(n * log(n))，其中n是數組的元素個數。
     • 在這個程序中，numNumbers是5，所以排序的時間復雜度為O(5 * log(5))。

2. 查找 (bsearch)：

   • 時間復雜度：O(log(n))
     • bsearch使用二分查找算法，其時間復雜度為O(log(n))，其中n是數組的元素個數。
     • 在這個程序中，數組已經排好序，numNumbers是5，所以查找的時間復雜度為O(log(5))。

因此，整個程序的時間復雜度主要由排序的部分決定，為O(5 * log(5))。在大O表示法中，忽略常數項，這可以簡化為O(log(5))，即O(1)。因此，總體時間復雜度可以近似看作是O(1)，即常數時間。這意味著程序的運行時間與數組的規模無關，對于小規模的數組來說是非常高效的。

總結

這個簡單的C程序演示了如何使用qsort對數組進行排序，然后使用bsearch進行二分查找。這兩個函數是C標準庫中用于排序和查找的強大工具，通過傳遞比較函數，我們可以適應不同的數據類型和排序/查找需求。在實際編程中，這種方法能夠提高效率，并且是一種常見的編程實踐。