Binary search, O(log2(N)), fix regular binary search not working for some cases
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nFixed bug in binary search, search from 10, 100, 1000 ... return whenever
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nFixed bug in binary search, search from 10, 100, 1000 ... return whenever the parts is too big or correct size\n\n# Complexity\n- Time complexity:\nO(log2(N))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<string> splitMessage(string message, int limit) {\n\n        vector<string> ans;\n\n        if(limit>=message.size()+5) {\n            ans.push_back(message+"<1/1>");\n        }\n\n        int sufLen[5];\n        sufLen[0] = 0;\n        sufLen[1] = 6*9; // first 9 with two digit, 10<= len <100\n        sufLen[2] = sufLen[1]+9 + 90*(3+5); // first 99 with 3 digit, 100=<len<1000\n        sufLen[3] = sufLen[2]+99 + 900*(3+7); // first 999 with 4 digit, 1000=<len<10000\n        sufLen[4] = sufLen[3]+999 + 9000*(3+9); //10^4\n\n        int n = message.size();\n        int left =n/limit;\n        int right = n*(1+3+10)/limit;\n\n        int parts, res, minParts = -1;;\n        while(left<=right) {\n            parts = (left+right)/2;\n            res = testSplit(n, limit, parts, sufLen);\n            if(res==1) {\n               break;\n            }\n            else if(res==0) {\n                left = parts+1;\n            } else {\n                right = parts-1;\n            }\n        }\n        \n        if(res!=1) return ans;\n        return splitMessage2(message, limit, parts);\n    }\n\nprivate:\n\n    int countDigits(int n) {\n        int count = 1;\n        while(n/10>0) {\n            count++;\n            n = n/10;\n        }\n        return count;\n    }\n\n    int testSplit(int total, int limit, int &parts, int* sufLen) {\n        int res;\n        int digNum = countDigits(parts);\n        int tenpow = 10;\n\n        while(parts>=tenpow) {\n            res = testSplit2(total, limit, tenpow-1, sufLen); // use 9, 99, 999 as parts first\n             if(res>=1) { // too big or fit, don\'t need to go to next digit\n                parts = tenpow-1;\n                return res;\n            }\n            tenpow *= 10;\n        }\n        return testSplit2(total, limit, parts, sufLen);\n    }\n    \n    int testSplit2(int total, int limit, int parts, int* sufLen) {\n        \n        int digNum = countDigits(parts);\n        int i = digNum;\n        int tenpow = 1;\n        while(i>0) {\n            tenpow *= 10;\n            i--;\n        }\n\n        int lastSufSize = (3+2*digNum) ;\n        int sufLen2 = sufLen[digNum-1] + (parts-(tenpow/10-1))*lastSufSize;\n\n        if(lastSufSize>=limit) return 2; // parts size too big\n        if(parts*limit<total+sufLen2) return 0; //too small\n        if(parts*limit>=total+sufLen2 && (parts-1)*limit<total+sufLen2-lastSufSize) return 1; // fit\n        else return 2; // too big\n    }\n\n    vector<string> splitMessage2(string message, int limit, int parts) {\n         vector<string> res;\n\n         string sp2 = "/"+ to_string(parts) + ">";\n         int curPos=0;\n         for(int i=0;i<parts-1;i++) {\n            string sp1 = "<"+ to_string(i+1) + sp2;\n            int k = limit - sp1.size();\n            string curStr = message.substr(curPos, k);\n            res.push_back(curStr+sp1);\n            curPos += k;\n         }\n\n        string sp1 = "<"+ to_string(parts) + sp2;\n        int k = message.size()-curPos;\n        string curStr = message.substr(curPos, k);\n        res.push_back(curStr+sp1);\n        return res;\n\n    }\n};\n```
['C++']