三、 给定一个由n个互不相同的数所组成的集合S。请利用分治思想设计一个算法，找出S的中位数。（所谓中位数是指，当n为奇数时，处于中间位置的数值即为中位数；当n为偶数时，中位数则为处于中间位置的2个数的平均值。）分析该算法的时间复杂度。

这是一个典型的使用分治思想的问题。我们可以基于快速排序的思想来解决这个问题：每次选择一个pivot元素，把小于pivot的元素放在左边，大于pivot的元素放在右边，然后递归地处理左右两个部分，直到找到中位数为止。

具体地，我们可以选择数组中的一个元素作为pivot，然后把数组分成两部分：小于pivot的元素和大于pivot的元素。如果小于pivot的元素个数大于n/2，那么中位数一定在左半部分，否则中位数一定在右半部分。然后我们可以递归地处理左半部分或右半部分，直到找到中位数为止。

时间复杂度分析：每次划分的时间复杂度为O(n)，递归的层数为O(logn)，因此总的时间复杂度为O(nlogn)。

代码实现（Python）如下：

def find_median(arr):
    n = len(arr)
    if n % 2 == 1:
        k = n // 2
    else:
        k = n // 2 - 1
    return quick_select(arr, k)

def quick_select(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    if len(left) == k:
        return pivot
    elif len(left) > k:
        return quick_select(left, k)
    else:
        return quick_select(right, k - len(left) - 1)

其中，find_median是主函数，quick_select是实现快速选择的函数。