Divide and Conquer

求众数：（leetcode 169）

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
      
        def dnc(low, high):
            if low == high:
                return nums[low]
            
            mid = low + (high - low) // 2
            left_res = dnc(low, mid)
            right_res = dnc(mid+1, high)
            
            c1, c2 = 0, 0
            for i in range(low,high+1):
                if nums[i] == left_res:
                    c1+=1
                if nums[i] == right_res:
                    c2+=1

            return left_res if c1 > c2 else right_res
        
        l = len(nums)
        return dnc(0, l-1)

        

寻找数组中的最小值：

class Solution:

    def findMin(self, nums: List[int]) -> int:
        def dnc(low,high):
            if low == high:
                return nums[low]
            
            mid = low + (high-low) // 2
            left_res = dnc(low, mid)
            right_res = dnc(mid+1, high)
            return left_res if left_res < right_res else right_res

                    
        l = len(nums)
        return dnc(0,l-1)