//回报本版,码遍本版
//Given a string of sorted integers, e.g. "1 52 69 456789 994546566";
//and a a number e.g. 69.
//You need to tell if it is in the input, e.g. 69=>true.
//strlen is O(n), don't use C style string for O(log n), suppose
//the string is friendly without lots of blank.
void GetWordPos(const char *mid, const char *left, const char *right, const
char **pstart, const char **pend){
while (isspace(*mid))
++mid;
*pstart = mid;
while (*pstart >= left && !isspace(**pstart))
--(*pstart);
if (isspace(**pstart))
++(*pstart);
*pend = mid;
while (*pend < right && !isspace(**pend))
++(*pend);
}
int StrCmp(const char *numstr, int numlen, const char *pstart, const char *
pend){
int len = pend - pstart;
if (numlen < len){
return -1;
} else if (numlen > len){
return 1;
} else {
while (*numstr && *numstr == *pstart){
++numstr;
++pstart;
}
if (!*numstr){
return 0;
} else if (*numstr < *pstart){
return -1;
} else {
return 1;
}
}
}
void IntToStr(int num, char *numstr, int *numlen){
//todo
return;
}
bool SearchString(const char *str, int num){
if (!str)
return false;
int len = strlen(str);
int left = 0;
int right = len;
char numstr[128];
int numlen = 0;
IntToStr(num, numstr, &numlen);
while (left < right){
int mid = left + (right - left) / 2;
const char *pstart, *pend;
GetWordPos(str + mid, str + left, str + right, &pstart, &pend);
int ret = StrCmp(numstr, numlen, pstart, pend);
if (ret == 0){
return true;
} else if (ret < 0){
right = pstart - 1 - str;
} else {
left = pend + 1 - str;
}
}
return false;
}