在一百万个字符的字符串中搜索一个字符
Search one character in a million characters string
在一百万个字符的字符串中搜索一个字符的最佳方法是什么？这更多是从算法的角度来看，而不是如何用特定的编程语言来做？
二分查找是一种好方法吗？
不进行预处理，扫描字符串直到遇到目标字符。如果您只需要检查第一个实例的存在或位置，您就完成了。否则需要扫描到最后。
有预处理
如果您需要报告存在或计数，请形成直方图（每个可能值的实例计数）；这可以在一次通过中完成（如果不需要计数，可能会提前终止）。然后在恒定时间内完成查询。
如果您需要报告第一个（或多个）实例，请为每个字符值填写一个 table 的首次出现索引；这可以一次性完成（可能提前终止）。然后在恒定时间内完成查询。
如果您需要报告所有实例，您可以预填link每个角色的所有实例的列表；这可以一次性完成，但存储成本很高（每个字符一个 link）。然后按出现次数按比例完成一次查询。
请注意，使用一般排序进行排序，然后通过二分查找回答查询可能是最糟糕的事情。一般排序会比需要的更昂贵（N Log(N) 而不是 N），并且查询会很昂贵（Log(N) 而不是 1）。不算在内，如果您需要位置信息，则必须在排序前用额外的字段扩充字符串。
如果已知字符串中的字符是按排序顺序排列的（这种情况极不可能发生！），答案就不同了：
如果您只需要查询一次，请使用二分法搜索（如果您被问及找到字符的计数或范围，则使用二分法搜索）。
如果你需要执行更多的查询（至少S Log(S)，其中S是字母表的大小），那么你可以通过一系列二分法来分隔相等字符的范围搜索。
设 L 为字符串长度，S 为字母大小。
没有预处理，你需要顺序搜索。它将进行多次比较，等于目标字符第一次出现的位置（如果不存在则为 L）。最佳情况 1，最坏情况 L，平均情况 LS/K（对于目标字符出现 K 次的均匀且平衡的分布）。
通过预处理，您可以通过字符串的顺序扫描来填充存在 table。字符比较的次数将等于任何字符的“最后”第一次出现（如果没有字符则为 L）。最佳情况 S，最坏情况 L。需要额外存储 S 位。后续查询在恒定时间内完成。
在一百万个字符的字符串中搜索一个字符的最佳方法是什么？这更多是从算法的角度来看，而不是如何用特定的编程语言来做？
二分查找是一种好方法吗？
不进行预处理，扫描字符串直到遇到目标字符。如果您只需要检查第一个实例的存在或位置，您就完成了。否则需要扫描到最后。
有预处理
如果您需要报告存在或计数，请形成直方图（每个可能值的实例计数）；这可以在一次通过中完成（如果不需要计数，可能会提前终止）。然后在恒定时间内完成查询。
如果您需要报告第一个（或多个）实例，请为每个字符值填写一个 table 的首次出现索引；这可以一次性完成（可能提前终止）。然后在恒定时间内完成查询。
如果您需要报告所有实例，您可以预填link每个角色的所有实例的列表；这可以一次性完成，但存储成本很高（每个字符一个 link）。然后按出现次数按比例完成一次查询。
请注意，使用一般排序进行排序，然后通过二分查找回答查询可能是最糟糕的事情。一般排序会比需要的更昂贵（N Log(N) 而不是 N），并且查询会很昂贵（Log(N) 而不是 1）。不算在内，如果您需要位置信息，则必须在排序前用额外的字段扩充字符串。
如果已知字符串中的字符是按排序顺序排列的（这种情况极不可能发生！），答案就不同了：
如果您只需要查询一次，请使用二分法搜索（如果您被问及找到字符的计数或范围，则使用二分法搜索）。
如果你需要执行更多的查询（至少S Log(S)，其中S是字母表的大小），那么你可以通过一系列二分法来分隔相等字符的范围搜索。
设 L 为字符串长度，S 为字母大小。
没有预处理，你需要顺序搜索。它将进行多次比较，等于目标字符第一次出现的位置（如果不存在则为 L）。最佳情况 1，最坏情况 L，平均情况 LS/K（对于目标字符出现 K 次的均匀且平衡的分布）。
通过预处理，您可以通过字符串的顺序扫描来填充存在 table。字符比较的次数将等于任何字符的“最后”第一次出现（如果没有字符则为 L）。最佳情况 S，最坏情况 L。需要额外存储 S 位。后续查询在恒定时间内完成。