这是对字符串数组执行二进制搜索的合理方法吗

Question

给定：

1. 所有使用的字符串都只包含ASCII字符
2. 已经定义了一个以128为基数的整数类型。128来自我们预期的可能的字符数
3. 尽管不支持大多数基本操作，但可以实现将这些基于128的整数中的一个与另一个进行比较(<，>，=)
4. 我们的数据存储在一个以128为基数的整数数组中，每个整数代表一个字符串

分拣过程如下所示：

1. 将所有给定的字符串转换为以128为基数的整数。这可以通过让每个ASCII字符在每个地方表示不同的值来实现。将这些存储在阵列中
2. 使用基于128的整数类中定义的比较，使用通用排序算法

搜索过程如下所示：

1. 转换；搜索"；字符串转换为以128为基数的整数
2. 对以128为基的整数数组实现基本的二进制搜索方法，如果找到匹配值，则返回该值的索引

这似乎在大多数情况下都有效，但我想知道是否有更合理的方法来解决这个问题。

Answer 1

没有必要将字符串转换为数字。(巧合的是，它们似乎有完全相同的内存布局——转换是不操作的)。

你说

实现了将这些base-128整数中的一个与另一个进行比较(<，>，=)。

但这毫无意义。我们可以平等地陈述

实现了将这些字符串中的一个与另一个进行比较(<，>，=)。

(事实上确实存在)，而您所描述的只是">对字符串数组使用通用排序算法"；以及">在字符串数组上实现基本的二进制搜索方法"；。方法的描述变为空-是的，您可以通过执行X来执行X。

---

也就是说，不，这是一个时间复杂度很差的方法。词汇字符串比较(就像base-128整数比较一样)在字符串/整数的长度上是线性的。从字符串数组中实际构建trie并在其中进行搜索更有效。