###### tags: `APCS`
# **divideConquer**
### **題目解析**
這道題目要求在一個長度為 𝑛 的整數序列中，找出該序列中的最大值與最小值。題目特別要求使用分治法來解決這個問題。
### **解題方向**
* 分治法概念：
* 分治法是一種算法設計範式，主要思想是將一個問題分成若干個子問題，對每個子問題進行求解，然後將子問題的解合併成整個問題的解。
* 對於本題，我們可以將數列分成兩半，分別找到兩半中的最大值和最小值，然後將這兩個部分的最大最小值進行比較，從而得到整個數列的最大值和最小值。
* 步驟：
* 將數列不斷分割成左右兩部分，直到每部分只剩一個元素，此時最大值和最小值都為該元素本身。
* 對每個分割後的部分，遞迴地求解其最大值和最小值。
* 最後將左右兩部分的最大最小值進行比較，得出整個數列的最大最小值。
### **程式解析**
程式中，我們定義了一個遞迴函數 `search(arr, s, e)``，其中 arr 是輸入的整數序列，`s` 和 `e` 分別代表序列的起始和結束位置（不包含結束位置）。
* 基礎條件：
* 當序列只有一個元素時，直接返回該元素作為最大值和最小值。
* 遞迴分割：
* 將序列分成左右兩部分，分別對左右兩部分遞迴求解最大最小值。
* 合併結果：
* 合併左右兩部分的結果，找出最小值和最大值。
### **完整程式碼**

import sys

def search(arr, s, e):
    # 基礎條件：序列只有一個元素
    if s + 1 == e:
        return arr[s], arr[s]
    
    # 計算中間位置
    m = (s + e) // 2

    # 分別遞迴求解左右兩部分的最大最小值
    left_min, left_max = search(arr, s, m)
    right_min, right_max = search(arr, m, e)
    
    # 當往上回傳時：
    # 合併結果，找出整個序列的最小值和最大值
    return min(left_min, right_min), max(left_max, right_max)

for s in sys.stdin:
    data = list(map(int, s.split()))

    result_min, result_max = search(data, 0, len(data))
    print(result_min, result_max)