C 語言折半查找並插入保持有序：search 函數完整實現（降序數組版）

題目要求

• 已排序數組（降序：大→小）
• 折半查找 key
• 找到返回下標（0-based）
• 未找到 → 插入適當位置保持降序 → 返回特殊標識（如 -1 或 666）

完整代碼實現

// 假設數組容量足夠大（至少 n+1）
int search(int *d, int n, int key) {
    int low = 0, high = n - 1, mid;
    
    // 1. 標準折半查找（降序調整比較方向）
    while (low <= high) {
        mid = (low + high) / 2;
        if (key == d[mid]) return mid;           // 找到
        else if (key > d[mid]) high = mid - 1;   // key 更大，在左半部（降序）
        else low = mid + 1;                      // key 更小，在右半部
    }
    
    // 2. 未找到：low 是插入位置（首個 < key 的元素下標）
    //    降序數組：[0..low-1] >= key > [low..n-1]
    
    // 3. 向右移動元素騰空位置
    for (int i = n; i > low; i--) {
        d[i] = d[i - 1];
    }
    d[low] = key;  // 插入
    
    return -1;  // 約定：-1 表示「已插入」，>=0 表示「找到下標」
}

關鍵邏輯圖解（降序數組）

原數組：[90, 85, 80, 70, 60]  n=5
查找 key=75
low=0, high=4
mid=2, d[2]=80, 75<80 → low=3
mid=3, d[3]=70, 75>70 → high=2
循環結束：low=3, high=2
插入位置 = low = 3
移動：d[5]=d[4](60), d[4]=d[3](70), d[3]=75
新數組：[90, 85, 80, 75, 70, 60]  仍降序

升序數組版本（只需改比較方向）

// 升序：小→大
while (low <= high) {
    mid = (low + high) / 2;
    if (key == d[mid]) return mid;
    else if (key < d[mid]) high = mid - 1;  // key 更小，在左半部
    else low = mid + 1;                     // key 更大，在右半部
}
// 插入位置仍為 low
for (int i = n; i > low; i--) d[i] = d[i-1];
d[low] = key;

工程化注意事項

1. 數組容量檢查：調用前確保分配空間 ≥ n+1，否則越界。
2. 返回值語義：建議用結構體或輸出參數區分「找到」與「已插入」：

   typedef struct { int index; bool inserted; } SearchResult;
   

3. 重複鍵值策略：上述代碼插入後重複值在右側（穩定性），若需去重，查找到時直接返回不插入。
4. 邊界測試用例：

   
   // 空數組 n=0 → low=0 插入首位
   // key 最大 → low=0 插入頭部
   // key 最小 → low=n 插入尾部
   // key 介於兩值間 → low 指向首個 < key 的位置
   

標準庫替代方案（C++）

#include 
#include 
std::vector v = {90,85,80,70,60}; // 降序
auto it = std::lower_bound(v.begin(), v.end(), 75, std::greater());
v.insert(it, 75); // 自動移動元素，保持有序

折半查找 + 移動插入是「有序數組動態維護」的教科書級操作，掌握「low 即插入位置」不變式，升序/降序只需翻轉比較符號即可舉一反三。