申論題

三、二元搜尋法（binary search）使用 divide-and-conquer（分而治之）演算法 技巧，對一個已排序的（sorted）且長度為 n 的陣列 A[0:n–1]，以二元化 方 式 進 行 資 料 值 x 的 搜 尋 ， 其 最 差 時 間 複 雜 度 （ worst case time complexity）可降到。

(一)請使用 C++或 Python 語言，修改此二元 搜尋法，使其能對未排序的（unsorted）且長度為 n 的陣列 A[0:n1]，進 行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列， 並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜 尋，如果找到則回傳 1，如果找不到則回傳 0。（17 分） （注意：請寫一 個 searching 類別，內含一個 search 功能）