“Computer science empowers students to create the world of tomorrow.” - Satya Nadella, CEO of Microsoft

什麼是二分搜尋法?

不知道大家小時候有沒有玩過猜數字的遊戲，你的朋友會要你從0~100要猜到他心裡想的數字，你每猜一個數字，你的朋友都會提示你，你的數字是太大還是太小。

這種遊戲的最佳解法是什麼?答案就是：二分搜尋法！

每次都把數字的範圍砍半：第一次猜50，太大那就是把範圍變成0~50，太小就把範圍變成50~100，

第二次猜25或75，這就是二分搜尋法的概念，最壞的情況下，你只需要猜6~7次(log100)(以2為底)！

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

這道題目要找出target的index，而且要求O(log n)(以2為底)。

上面猜數字例子的陣列就是[0, 1, 2, 3,…,99, 100]，Example1則是[-1, 0, 3, 5, 9, 12]。

有沒有發現一個重要的事情? 那就是二分搜尋法的對象必須要是排序好的！這樣你取中間的數才會剛好把範圍給砍半。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        for num in nums:
            mid = (left + right) // 2
            guess = nums[mid]
            if guess < target: # 代表答案在右半部
                left = mid + 1 # +1是因為nums[mid]一定不是答案了，所以不用是left = mid！
            elif guess > target: # 代表答案在左半部
                right = mid - 1 # -1是因為nums[mid]一定不是答案了，所以不用是right = mid！
            else:
                return mid
        return -1

(Note: 使用Python以外的語言要考慮到(left + right) Overflow的問題，可以改成(right - left) / 2 + left)

什麼是貪心法?

貪心法(Greedy)的本質是局部最優解的總和等於全局最優解。

舉個例子：有個有錢人有5張支票，分別是[100, 1000, 2000, 3000, 5000]，他跟你說你每次可以拿一張支票走，最多可以拿三張，請問你要怎麼拿到最多錢?

每次(局部)都拿最大的支票(最優解)，三次下來就會是拿到最多錢的情形(全局最優解)。

455. Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

題目說：你的每個孩子想吃的餅乾大小g[1, 2, 3]，你的每個餅乾的大小s[1, 1]，請問你最多可以讓幾個孩子吃到滿意的餅乾大小?

苦思冥想後，你得到出一個”感覺”可行的解法，那就是把孩子想吃的餅乾大小g和每個餅乾的大小s先進行排序，然後大的餅乾優先餵胃口大的孩子，如果餅乾不能夠讓孩子滿意，那就換下個孩子(舉例來說：如果胃口大的孩子(想吃9吋的餅乾)，但你只有8吋餅乾，那就不要浪費，直接換下個孩子。

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort(reverse=True) # 大的排在前面
        s.sort(reverse=True)
        s_idx = 0
        cookies = len(s) # 總共有多少餅乾
        result = 0
        for i in range(0, len(g)):
            if s_idx < cookies and s[s_idx] >= g[i]: # s_idx表示正在發的餅乾索引不能大於餅乾的總數
                s_idx += 1 # 換下個餅乾
                result += 1
        return result 

為什麼剛剛說”感覺”?因為要證明這個貪心演算法是對的比想到這個貪心演算法還要困難很多，幾乎每種貪心問題都有不同的證明方法

因此，當你想要用貪心演算法的時候，你可能會先想想用幾個奇怪的測資帶入，如果感覺都沒問題，那就可以試試。之前比賽就有一個隊伍將貪心的演算法拿去用暴力解的答案做比對，沒問題了才提交！