Modify the binary search method

修改二元搜尋法

 二元搜尋法（binary search）使用 divide-and-conquer（分而治之）演算法

技巧，對一個已排序的（sorted）且長度為 n 的陣列 A[0:n1]，以二元化

方 式 進 行 資 料 值 x 的 搜 尋 ， 其 最 差 時 間 複 雜 度 （ worst case time

complexity）可降到(log n)。請使用 C++或 Python 語言，修改此二元

搜尋法，使其能對未排序的（unsorted）且長度為 n 的陣列 A[0:n1]，進

行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列，

並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜

尋，如果找到則回傳 1，如果找不到則回傳 0。（17 分）（注意：請寫一

個 searching 類別，內含一個 search 功能）請分析修改後的三元化搜尋

法其最差時間複雜度（worst case time complexity）以 order 的方式表示。

（8 分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。

以下是 Python 語言的程式碼，其中 searching 類別內含一個 search 函數，可以對未排序的陣列進行三元化搜尋：

class searching:

    def search(self, arr, x):

        return self.ternary_search(arr, 0, len(arr) - 1, x)

    def ternary_search(self, arr, l, r, x):

        if r >= l:

            mid1 = l + (r - l) // 3

            mid2 = r - (r - l) // 3

            if arr[mid1] == x:

                return 1

            if arr[mid2] == x:

                return 1

            if x < arr[mid1]:

                return self.ternary_search(arr, l, mid1 - 1, x)

            elif x > arr[mid2]:

                return self.ternary_search(arr, mid2 + 1, r, x)

            else:

                return self.ternary_search(arr, mid1 + 1, mid2 - 1, x)

        return 0

此程式碼中，searching 類別內含一個 search 函數，可以對未排序的陣列進行三元化搜尋。在 search 函數中，我們調用了 ternary_search 函數來實現三元化搜尋。在 ternary_search 函數中，我們首先計算出兩個中間索引 mid1 和 mid2，然後根據目標值與這兩個索引所對應的元素的大小關係，遞歸地搜索可能包含目標值的子陣列。

最差時間複雜度為 O(log3n)。因為每次遞歸都會將陣列切成三個子陣列，所以最壞情況下，我們需要遞歸 log3n 層才能找到目標值。因此，最差時間複雜度為 O(log3n)。