二分查找本身不難理解，難在巧妙地運用二分查找技巧。對於一個問題，你可能都很難想到它跟二分查找有關，比如前文 最長遞增子序列就藉助一個紙牌遊戲衍生出二分查找解法。
今天再講一道巧用二分查找的算法問題：如何判定字符串s是否是字符串t的子序列（可以假定s長度比較小，且t的長度非常大）。舉兩個例子：
s = "abc", t = "ahbgdc", return true.
s = "axc", t = "ahbgdc", return false.
題目很容易理解，而且看起來很簡單，但很難想到這個問題跟二分查找有關吧？
一、問題分析首先，一個很簡單的解法是這樣的：
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
while (i < s.size() && j < t.size()) {
if (s[i] == t[j]) i++;
j++;
}
return i == s.size();
}
其思路也非常簡單，利用雙指針i, j分別指向s, t，一邊前進一邊匹配子序列：
讀者也許會問，這不就是最優解法了嗎，時間複雜度只需 O(N)，N 為t的長度。
是的，如果僅僅是這個問題，這個解法就夠好了，不過這個問題還有 follow up：
如果給你一系列字符串s1,s2,...和字符串t，你需要判定每個串s是否是t的子序列（可以假定s相對較短，t很長）。
boolean[] isSubsequence(String[] sn, String t);
你也許會問，這不是很簡單嗎，還是剛才的邏輯，加個 for 循環不就行了？
可以，但是此解法處理每個s時間複雜度仍然是 O(N)，而如果巧妙運用二分查找，可以將時間複雜度降低，大約是 O(MlogN)，M 為 s的長度。由於 N 相對 M 大很多，所以後者效率會更高。
二、二分思路二分思路主要是對t進行預處理，用一個字典index將每個字符出現的索引位置按順序存儲下來（對於 ASCII 字符，可以用大小為 256 的數組充當字典）：
比如對於這個情況，匹配了 "ab"，應該匹配 "c" 了：
按照之前的解法，我們需要j線性前進掃描字符 "c"。但現在藉助index中記錄的信息，可以二分搜索index[c]中比 j 大的那個索引，在上圖的例子中，就是在[0,2,6]中搜索比 4 大的那個索引：
這樣就可以快速得到下一個 "c" 的索引 6。現在的問題就是，如何用二分查找計算那個恰好比 4 大的索引呢？答案是，尋找左側邊界的二分搜索就可以做到。
在前文 二分查找算法詳解中，詳解了如何正確寫出三種二分查找算法的細節。二分查找返回目標值val的索引，對於搜索左側邊界的二分查找，有一個特殊性質：
當val不存在時，得到的索引恰好是比val大的最小元素索引。
什麼意思呢，就是說如果在數組[0,1,3,4]中搜索元素 2，算法會返回索引 2，也就是元素 3 的位置，元素 3 就是數組中大於 2 的最小元素。所以我們可以利用二分搜索避免線性掃描。
以上就是搜索左側邊界的二分查找，等會兒會用到，其中的細節可以參見 二分查找算法詳解，這裡不再贅述。
四、代碼實現這裡以處理單個字符串s為例，對於多個字符串s，把預處理部分單獨抽出來即可。
算法執行的過程是這樣的：
可見藉助二分查找，算法的效率是可以大幅提升的：預處理時需要 O(N) 時間，每次匹配子序列的時間是 O(MlogN)，比之前每次匹配都要 O(N) 的時間要高效得多。
當然，如果只需要判斷一個 s 是否是 t 的子序列，是不需要二分查找的，一開始的 O(N) 解法就是最好的，因為雖然二分查找解法處理每個 s 只需要 O(MlogN)，但是還需要 O(N) 時間構造 index 字典預處理，所以處理單個s時沒有必要。
以上就是二分查找技巧判定子序列的全部內容，希望你能有所收穫。
●編號1041，輸入編號直達本文
●輸入m獲取文章目錄
程式設計師數學學習
鍛鍊數學邏輯思維