C語言指標陣列進階：字串二分搜尋與有序插入完整實作

指標陣列應用場景

指標陣列（char *ptr[N]）常用於儲存多條字串，每個元素指向動態分配的字串緩衝區。優點：字串長度可變、排序/插入時僅交換指標、不移動實際字串資料，效率高。

範例 1：已排序字串指標陣列的二分搜尋

演算法步驟

1. 輸入 n 條字串至指標陣列（按字典序）。
2. 設 low=0, high=n-1, mid=(low+high)/2。
3. 比較 ptr[mid] 與目標字串：

• 目標較小 → high = mid-1
• 目標較大 → low = mid+1
• 相等 → 回傳找到的字串指標

4. 重複直到 low > high，未找到回傳 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 str;  // 找到
    }
    return NULL;  // 未找到
}

主程式動態配置每字串 20 位元組緩衝區（malloc(20)），讀入 5 條字串後呼叫 binary() 搜尋。

範例 2：有序字串指標陣列插入新字串

插入邏輯

1. 先用二分搜尋找出插入位置 i（0~n）。
2. 將 i 之後的指標向後搬移：for(j=n; j>i; j--) ptr[j] = ptr[j-1];
3. 將新字串複製至 ptr[i]。

二分搜尋插入位置函數

int binary(char *ptr[], char *str, int n) {
    int low = 0, high = n-1, mid;
    if (strcmp(str, ptr[0]) < 0) return 0;      // 插入最前
    if (strcmp(str, ptr[high]) > 0) return n;   // 插入最後
    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 mid;  // 重複字串，插入該位置
    }
    return low;  // 中間位置
}

插入函數

void insert(char *ptr[], char *str, int n, int i) {
    for (int j = n; j > i; j--)
        strcpy(ptr[j], ptr[j-1]);  // 向後搬移
    strcpy(ptr[i], str);           // 放入新字串
}

記憶體管理關鍵點

• 陣列大小宣告為 ptr[6]，預留一個空位給插入。
• 所有 6 個指標皆 malloc(20) 配置緩衝區，確保搬移時不會越界。
• 字串長度以最長者為準配置空間，避免 strcpy 溢位。

執行流程示意

1. 輸入 5 條已排序字串。
2. 輸入欲插入字串。
3. 呼叫 binary() 取得插入索引 i。
4. 呼叫 insert() 完成插入。
5. 輸出 6 條字串驗證順序。

此技巧廣泛應用於編輯器緩衝區、命令歷史、動態選單等需維持順序的字串集合管理。