考虑用向量存放一组字符串。为在其中进行二分查找,可依据字典序确定字符串之间的次序:
设字符串a = a1a2...an 和b = b1b2...bm
则 a < b 当且仅当 n = 0 < m,或者 a1 < b1,或者 a1 = b1,
也就是说,两个字符串之间的大小关系,取决于它们(按首字符对齐后)第一对互异的字符。
a) 试实现一个字符串类,幵提供相应的比较器,或者重载对应的操作符;
b)若共有n个字符串,二分查找的复杂度是否仍为O(logn)?