現在我們來用二分搜尋來解這題，數學推導太長了而且網上還蠻多的就先跳過…

我們用紙牌遊戲代替一下，這個規則就是

1.只能把排放到比目前牌面比較小的那疊

(圖)

2.如果每一疊都比牌面小，則右邊新建一疊，然後把這張牌放到新的一疊去

(圖)

3.如果同時有多疊都可以放置，則放置到最左邊的那疊

(圖)

4.在結束後，從最右邊開始，往回排列出最長遞增子序列

(圖)

然後我們將處理撲克牌的過程，用程式設計出來即可，每次處理一張撲克牌，要先尋找一個合適的牌堆來放，而最後牌堆頂的牌有序，如此便能使用二分搜尋，透過二分搜尋找尋目前要處理的撲克牌應該擺放的位置．

有了這些概念我們來實做看看

fun lengthOfLISBinary(nums: Array<Int>):Int{
    val top =  IntArray(nums.size)
    var piles = 0//牌堆初始為0
    for(i in nums.indices){
        val poker = nums[i] //待處理的牌
        
        var left = 0
        var right = piles
        while(left<right){
            val mid = left + (right - left) / 2
            when {
                top[mid]>poker -> {
                    right = mid
                }
                top[mid]<poker -> {
                    left = mid+1
                }
                else -> {
                    right = mid
                }
            }
        }
        
        //沒有找到可以放置的牌堆，新建立一個
        if(left == piles){
            piles++
        }
        top[left] = poker
    }
    return piles //排堆的總數就是LIS的總數
}

這個做法很難去想到，首先第一步要先進行數學證明，才能利用紙牌遊戲的規則，推導出獲得LIS的值．然後有了規則，又要想到使用二分搜尋法進行優化．而在寫二分搜尋法時，又要很注重細節．才能夠寫得正確．

所以，一般來說還是使用昨天的動態規劃版本就好，利用數學歸納法簡單好懂些．