C語言實作：字串中數字提取與排序、山脈陣列二分查找演算法解析

編輯：關於C語言

前言

在程式設計面試與實務開發中，字串處理與陣列搜尋是兩大經典主題。本文將深入解析兩個實用的演算法問題：第一，從混雜字串中提取數字並排序輸出；第二，在「先增後減」的山脈陣列中高效查找目標值。我們將提供完整的 C++ 實作碼、邏輯解析與邊界條件處理，幫助讀者建立扎實的演算法思維。

一、字串數字提取與排序

問題描述

給定一個包含字母與數字的字串，例如 ad2ef35adx1wewe76，其中數字部分為 2、35、1、76（連續數字視為一個整數）。要求提取所有數字，按從小到大排序，並以 - 連接輸出，如 1-2-35-76。函數原型為 void fun(char* src, char* des)。

核心思路

掃描字串：遍歷字元，利用 isdigit() 判斷是否為數字。
組合多位數：遇到數字時，持續向後讀取直到非數字，將連續數字轉為整數（res = res * 10 + (ch - '0')）。
儲存與排序：將提取的整數存入 vector<int>，呼叫 sort() 排序。
格式化輸出：遍歷排序後的陣列，寫入目的緩衝區，數字間以 - 分隔。

C++ 參考實作

#include <vector>
#include <algorithm>
#include <cctype>
#include <cstdio>

void fun(const char* src, char* des) {
    std::vector<int> nums;
    int val = 0;
    bool inNumber = false;

    while (*src) {
        if (std::isdigit(*src)) {
            val = val * 10 + (*src - '0');
            inNumber = true;
        } else if (inNumber) {
            nums.push_back(val);
            val = 0;
            inNumber = false;
        }
        ++src;
    }
    if (inNumber) nums.push_back(val); // 處理字串結尾為數字的情況

    std::sort(nums.begin(), nums.end());

    char* p = des;
    for (size_t i = 0; i < nums.size(); ++i) {
        p += std::sprintf(p, "%d", nums[i]);
        if (i + 1 < nums.size()) *p++ = '-';
    }
    *p = '\0';
}

關鍵細節

使用 inNumber 標記避免重複 push_back。
迴圈結束後需檢查是否有未存入的數字（字串以數字結尾）。
sprintf 回傳寫入字元數，方便指針移動，效率優於 strcat。

二、山脈陣列（先增後減）的二分查找

問題描述

給定一個陣列，元素先嚴格遞增後嚴格遞減（如 {2, 3, 4, 5, 10, 7, 6, 1}），設計演算法查找目標值的索引，時間複雜度要求 O(log n)。

演算法策略：三步走

找峰值（最大值索引）：利用二分查找特性，比較 mid 與左右鄰居，決定峰值在左半部還是右半部。
左半部遞增區間二分查找：標準二分查找。
右半部遞減區間二分查找：邏輯反轉，arr[mid] > target 時向右搜尋。

找峰值邏輯圖解

山脈陣列峰值查找示意圖

完整 C++ 實作

#include <iostream>
#include <vector>

int findPeak(const std::vector<int>& arr) {
    int lo = 0, hi = arr.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < arr[mid + 1])
            lo = mid + 1;      // 峰值在右側
        else
            hi = mid;          // 峰值在左側或即為 mid
    }
    return lo; // lo == hi
}

int binSearchAsc(const std::vector<int>& arr, int lo, int hi, int target) {
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int binSearchDesc(const std::vector<int>& arr, int lo, int hi, int target) {
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) lo = mid + 1; // 遞減區間邏輯反轉
        else hi = mid - 1;
    }
    return -1;
}

int searchMountainArray(const std::vector<int>& arr, int target) {
    int peak = findPeak(arr);
    if (arr[peak] == target) return peak;
    int idx = binSearchAsc(arr, 0, peak - 1, target);
    if (idx != -1) return idx;
    return binSearchDesc(arr, peak + 1, arr.size() - 1, target);
}