7-9 二分查找字符
目录
题目描述
输入一行，首先是一个不包含空格的字符串s，接着是一个字符c，字符和字符串之间用空格隔开，字符串长度小于等于1000，使用二分查找算法在s中查找c，输出c所在的下标（下标从0开始）。若c不存在，输出-1。
输入格式:
输入在一行中给出1个长度不超过1000的字符串s和字符c，中间用空格隔开。
输出格式:
在一行中输出c在s中的位置，位置从0开始，如果c不在s中，输出-1。
输入样例:
在这里给出一组输入。例如：
abcefhi f
输出样例:
在这里给出相应的输出。例如：
4
题目要求使用二分，却没告知字符串中的字符是从小到大递增的，同样有两种解法
详细请看：7-4 二分查找
详细代码（手写二分）：
#include<iostream> using namespace std; int main() { string s,c; cin>>s>>c; int l=0,r=s.length()-1;//左端点为0，右端点为s.length()-1，因为他们的下标是0到s.length()-1 while(l<r) { int mid=(l+r)/2; if(s[mid]<c[0])//如果当前值小于要查找的值，往右移动，说明查找的值还在右边，需要大一点 { l=mid+1; } else//如果当前值大于等于要查找的值，往左移动，说明查找的值还在左边吗，需要小点 { r=mid; } } if(s[l]==c[0])//如果查找下标不是需要查找的元素 cout<<l; else cout<<-1; }
详细代码（使用自带函数）：
#include<iostream> using namespace std; const int N=1e6+7; string s,c; int main() { cin>>s>>c; int t=lower_bound(s.begin(),s.end(),c[0])-s.begin();//查找第一个小于等于需要查找元素的地址，减去字符串的首地址则为下标 if(t>=s.length()||s[t]!=c[0])//不在字符串的长度内，或者找到的下标与目标不符合 { cout<<-1; } else { cout<<t; } }
原文地址：https://blog.csdn.net/qwertf123/article/details/144776667
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！