C語言有序二維陣列查找：從右上角開始的最佳搜尋策略

題目重述

在一個「每行遞增、每列遞增」的二維陣列中，判斷目標數值是否存在。本文提供的程式碼已正確實作右上角搜尋法，時間複雜度 O(m+n)。以下將詳細解析其運作原理與關鍵細節。

核心演算法邏輯

int search_target(int arr[], int target, int ROW, int COLUMN) {
    int row = 0;
    int column = COLUMN - 1;  // 起始：右上角

    if (arr != NULL && ROW > 0 && COLUMN > 0) {
        while (row < ROW && column >= 0) {
            int current = arr[row * COLUMN + column]; // 一維索引轉換
            if (current == target) return 1;          // 找到
            else if (current < target) ++row;         // 往下：捨棄該行
            else --column;                            // 往左：捨棄該列
        }
        return 0; // 未找到
    }
    return 0;
}

為什麼選擇右上角（或左下角）？

左上角與右下角無法單向刪減搜尋空間，故不適合。

一維索引轉換技巧

函式參數接收 `int arr[]`（實為 `int *`），呼叫端傳入 `int arr[][3]` 會隱性轉型為 `int (*)[3]`，再轉為 `int *`。存取元素需手動計算：index = row * COLUMN + col。此技巧常用於將二維陣列攤平傳遞給通用函式。

完整可執行程式

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 

int search_target(int arr[], int target, int ROW, int COLUMN) {
    int row = 0, column = COLUMN - 1;
    if (arr && ROW > 0 && COLUMN > 0) {
        while (row < ROW && column >= 0) {
            int val = arr[row * COLUMN + column];
            if (val == target) return 1;
            else if (val < target) row++;
            else column--;
        }
    }
    return 0;
}

int main() {
    int arr[][3] = { {1,2,3}, {4,5,6}, {7,8,9} };
    int target = 7;
    int ret = search_target((int *)arr, target, 3, 3);
    printf(ret ? "exist\n" : "not exist\n");
    system("pause");
    return 0;
}

常見錯誤提醒

1. 索引計算錯誤：忘記乘 `COLUMN` 會導致存取錯誤記憶體。
2. 邊界條件：`while (row < ROW && column >= 0)` 必須嚴格檢查，避免越界。
3. 參數驗證：檢查 `arr != NULL` 且 `ROW, COLUMN > 0` 是良好防禦性程式設計習慣。

擴展應用

• LeetCode 240. Search a 2D Matrix II：完全相同題型。
• 變體：計數目標出現次數：找到後繼續搜尋（往左+往下），累加計數。
• 變體：回傳座標：修改回傳型別為結構體或雙指標輸出行列索引。

總結

有序二維陣列查找的最佳解法是「右上角/左下角搜尋法」，利用單調性每次刪減一行或一列，達到 O(m+n) 時間、O(1) 空間。本文程式碼正確實作此邏輯，並示範一維指標模擬二維存取的實用技巧。