指標陣列（二）：有序字符指標陣列的二分查找實現

範例：有序字符指標陣列的二分查找

字符串按字典序排序存於指標陣列，採用二分查找（折半查找）算法：

1. 設 low 指向陣列低端，high 指向高端，mid = (low+high)/2
2. 比較 mid 指向的字符串與目標串
3. 若目標較小，在 low~mid-1 區間；若較大，在 mid+1~high 區間
4. 調整 low/high，重新計算 mid，重複直到找到或區間為空

完整程式碼

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

char *binary(char *ptr[], char *str, int n);  // 函數聲明

int main() {
    char *ptr1[5], *temp;
    int i, j;
    
    // 輸入 5 個按字典序排序的字符串
    for (i = 0; i < 5; i++) {
        ptr1[i] = (char *)malloc(20);
        gets(ptr1[i]);
    }
    
    printf("\n原始字符串:\n");
    for (i = 0; i < 5; i++)
        printf("%s\n", ptr1[i]);
    
    printf("輸入查找字符串:\n");
    temp = (char *)malloc(20);
    gets(temp);
    
    temp = binary(ptr1, temp, 5);  // 調用查找
    if (temp)
        printf("查找成功 ----- %s\n", temp);
    else
        printf("查找失敗！\n");
    
    // 釋放記憶體（略）
    return 0;
}

// 折半查找函數：返回找到的字符串指標，失敗返回 NULL
char *binary(char *ptr[], char *str, int n) {
    int low = 0, high = n - 1, mid;
    
    while (low <= high) {
        mid = (low + high) / 2;
        int cmp = strcmp(str, ptr[mid]);
        if (cmp < 0)
            high = mid - 1;
        else if (cmp > 0)
            low = mid + 1;
        else
            return ptr[mid];  // 找到，返回目標字符串指標
    }
    return NULL;  // 未找到
}

關鍵點

• ptr1 是 char* 陣列，每個元素指向一個動態分配的字符串
• strcmp 返回負/零/正分別表示小於/等於/大於
• 二分查找要求陣列預先有序
• 時間複雜度：O(log n)，遠優於線性查找 O(n)
• 記得釋放 malloc 分配的記憶體（範例中省略）