首页 > 试题广场 >

考虑用向量存放一组字符串。为在其中进行二分查找,可依据字典序

[问答题]

考虑用向量存放一组字符串。为在其中进行二分查找,可依据字典序确定字符串之间的次序:

设字符串a =  a1a2...an 和b =   b1b2...bm

 则 a < b 当且仅当 n = 0 < m,或者 a1  < b1,或者 a1  = b1
也就是说,两个字符串之间的大小关系,取决于它们(按首字符对齐后)第一对互异的字符。
a) 试实现一个字符串类,幵提供相应的比较器,或者重载对应的操作符;
b)若共有n个字符串,二分查找的复杂度是否仍为O(logn)?


这道题你会答吗?花几分钟告诉大家答案吧!