这个问题在这里已经有答案了：
在java中，如何确定数组是否包含特定值(29个答案）
上个月关门了。
我正在用java做一个小项目，我想让我的算法更高效。
我要做的是检查给定的字符串是否存在于字符串数组中。
问题是，我知道一些方法来检查字符串数组中是否存在字符串，但是我正在使用的数组非常大（大约90000个字符串），我正在寻找一种方法来提高搜索效率，而且我知道的唯一方法是基于线性搜索的，这对于这样规模的数组是不好的。
编辑：所以我试着实现给我的建议，但我写的代码没有正常工作，希望听到你的想法`
public static int binaryStringSearch(String[] strArr, String str) {
int low = 0;
int high = strArr.length -1;
int result = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (strArr[mid].equals(str)) {
result = mid;
return result;
}else if (strArr[mid].compareTo(str) < 0) {
low = mid + 1;
}else {
high = mid - 1;
}
}
return result;
}基本上，它应该返回字符串在数组中出现的索引，如果字符串不在数组中，则返回-1。
3条答案
按热度按时间fivyi3re1#
所以你有一个或多或少固定的字符串数组，然后你在代码中抛出一个字符串，它应该告诉你，如果你给它的字符串在数组中，我得到正确的吗？所以，如果你的数组几乎从不改变，就可以只按字母表排序，然后使用二进制搜索。汤姆斯科特在这方面做了一个很好的视频（如果你不想读一个长的，混乱的文本谁不是一个母语为英语的人写的，只要看这个，这就是你所需要的）。你只需看看中间，然后检查-你刚才读的是中间字符串之前还是之后的字符串？如果已经完全正确了，你可以停下来。但如果不是这样，您可以消除该字符串之后的所有字符串，以防它在您要查找的字符串之后，否则，可以消除在刚刚检查的字符串之前的所有字符串。当然，如果字符串本身不相等，也可以消除它，因为-逻辑。然后你再做一遍，检查剩下的字符串中间的字符串（顺便说一句，你不必实际删除数组项，只需为上下边界设置一个变量就足够了，因为你不会随机删除中间的元素）并根据结果消除。你这样做，直到列表中没有一个字符串。然后您可以确定您的输入不在数组中。所以这基本上意味着，通过检查和比较一个字符串，你不能像检查一个接一个那样只删除一个项目，你可以删除超过一半的数组，所以对于256个列表，应该只需要8个比较（或者9，不太确定，但我认为如果你不想找到这个项目，但知道它是否存在，需要一个更多）和65k（这几乎匹配你的数字）需要16。这是非常乐观的。
如果它还没有排序，你不能，因为这将需要太长的时间或某种原因，我不太清楚，我认为没有办法使它更快，如果它没有秩序，那么你必须检查他们一个接一个。
希望有帮助！
编辑：如果你不想对所有的项目进行真正的排序，只想让它快一点（26倍（如果语言是随机的话）），只需要为所有字母创建26个数组（如果你只使用普通字母，否则，使更多和速度提升也将增加），然后通过所有字符串循环，并把他们放入正确的数组匹配他们的第一个字母。这样比通常的排序要快得多，但这是一种折衷，因为它不如二进制搜索那么简洁。你基本上仍然使用线性搜索（=遍历所有项目并检查它们是否匹配），但你已经排序了这些项目。你可以想象，如果你想更快地找到一张table上的一叠纸牌，你可以用两种方法来排序，一种是懒惰的，另一种是不那么懒惰的。一种方法是按数字对所有卡片进行排序，假设卡片是从1到100的，但不是连续的，有丢失的卡片。但是很好地将它们分类，这样你就可以很快地找到任何卡片，这需要一些时间，所以你可以做的是制作10行卡片。在每一张牌中，你只是把你的牌按随机顺序排列，所以当有人想要38张牌时，你只需到第三行，然后线性搜索所有的牌，这样你就可以更快地找到物品，然后把它们随机放在你的table上，因为你只需要搜索十分之一的牌，但一旦你在那一排牌上，你就不能走捷径。
laik7k3q2#
如果需要，可以使用存储所有字符串的hashmap
包含查询非常频繁，查找字符串不经常更改。
内存不是问题（：d）。
5f0d552i3#
根据需求的不同，可以有很多方法来处理它。最好对可用的富api ootb使用一个collection类。
字符串是否应该是唯一的，即重复的字符串需要自动丢弃，并且插入顺序无关紧要：使用
Set<String> set = new HashSet<>()然后你可以用Set#contains检查特定字符串的存在。字符串是否应该是唯一的，即重复的字符串是否需要自动丢弃，插入顺序是否需要保留：使用
Set<String> set = new LinkedHashSet<>()然后你可以用Set#contains检查特定字符串的存在。列表不能包含重复的字符串。如果是，您可以使用
List<String> list = new ArrayList<>()从它丰富的api中获益，并且摆脱了固定大小的限制（注：元素的最大数量可以是Integer.MAX_VALUE)事先。然而，一个List总是按顺序导航。尽管有这个限制（或特性），但是可以通过对列表进行排序来获得一些效率（同样，这取决于您的需求）。检查为什么处理排序的数组比处理未排序的数组快？了解更多。