这是关于要点的类https://gist.github.com/2605302
我已经用不同的文件多次测试了它，即使对二进制搜索进行的比较较少，所花费的时间也总是更多。出了什么问题？
public static int linerSearch ( String array [], String word, long resultsArray [])
{
int comparisons = 0;
int pos = -1;
//i have started the timer where the search actualy starts
long start = System.nanoTime ();
for (int i = 0; i < array.length; i++){
comparisons = comparisons + 1;
if (array [i].equals (word)){
pos = i;
break;
}
}
long stop = System.nanoTime ();
long total = stop - start;
resultsArray [0] = total;
resultsArray [1] = (long) (long) array.length;
resultsArray [2]= (long) (long) comparisons;
return pos;
}
这是下一个二进制搜索类
public static int binarySearch (String [] array, String word, resultsArray []) {
int start = 0;
int end = array.length - 1;;
int midPt;
int pos = -1;
int comparisons2 = 0;
long start2 = System.nanoTime ();
Arrays.sort (array);
while (start <= end) {
midPt = (start + end) / 2;
comparisons2 = comparisons2 + 1;
if (array [midPt].equalsIgnoreCase (word)) {
pos = midPt;
break;
}
else if (array [midPt].compareToIgnoreCase (word) < 0) {
start = midPt + 1;
comparisons2 = comparisons2 + 1;
//camparisons2 addition was added inside this elseif and other elseif as a work around for not breaking the elseif statement tree, if it has made it two the last elseif then two camparisons after the first one will have been done
} else if (array [midPt].compareToIgnoreCase (word) > 0) {
comparisons2 = comparisons2 + 2;
end = midPt - 1;
}
}
long stop2 = System.nanoTime ();
long total2 = stop2 - start2;
resultsArray [0] = total2;
resultsArray [1] = (long) (long) array.length;
resultsArray [2]= (long) (long) comparisons2;
return pos;
}
编辑：我还应该补充一点，我在没有那行代码的情况下在以前排序过的数组上尝试过它，而且它不应该是更长的时间
你的基准测试的问题是 Arrays.sort(array( 需要大部分时间，并且 yoy 不计算它的比较。线性搜索需要 N 个比较。当您对数组进行排序时，您花费的比较超过 N 个。
要看到二叉搜索更快，您应该进行这样的测试：
1(通过线性搜索搜索不同的元素1000次
2(对数组进行一次排序，然后使用二叉搜索1000次搜索不同的元素
好的，我已经一劳永逸地为您解决了这个问题。首先，这是我使用的二叉搜索方法：
public static int binarySearch(String[] array, String word, long resultsArray[]) {
int start = 0;
int end = array.length - 1;
int midPt;
int pos = -1;
int comparisons2 = 0;
//Arrays.sort(array);
long start2 = System.nanoTime();
while (start <= end) {
midPt = (start + end) / 2;
int comparisonResult = array[midPt].compareToIgnoreCase(word);
comparisons2++;
if (comparisonResult == 0) {
pos = midPt;
break;
} else if (comparisonResult < 0) {
start = midPt + 1;
} else { // comparisonResult > 0
end = midPt - 1;
}
}
long stop2 = System.nanoTime();
long total2 = stop2 - start2;
resultsArray[0] = total2;
resultsArray[1] = (long) array.length;
resultsArray[2] = (long) comparisons2;
return pos;
}
您会注意到，我通过保存比较结果并使用它来减少比较次数。
接下来，我下载了这个235882单词列表。它已经排序忽略了大小写。然后，我构建了一个测试方法，该方法将该文件的内容加载到数组中，然后使用这两种搜索方法来查找该列表的每个单词。然后，它分别对每种方法的比较时间和次数求平均值。
我发现在选择使用哪种比较方法时必须小心：如果您Arrays.sort(...)列表并在二分搜索中使用compareToIgnoreCase，则失败！失败的意思是它无法从给定列表中找到该单词，即使该单词确实存在。这是因为Arrays.sort(...)是字符串的区分大小写的排序器。如果使用它，则必须对它使用 compareTo(...) 方法。
所以，我们有两个案例
- 不区分大小写的排序列表和
compareToIgnoreCase的使用 - 区分大小写的排序列表和
compareTo的使用
除了二叉搜索中的这些选项外，线性搜索中还有选项：是使用 equals 还是equalsIgnoreCase .我对所有这些情况进行了测试并进行了比较。平均结果：
- 带
equals的线性搜索：时间：725536 ns;比较：117941;时间/比较：6.15 ns - 线性搜索与
equalsIgnoreCase：时间：1064334 ns;比较：117940;时间/比较：9.02 ns - 带
compareToIgnoreCase的二叉搜索：时间：1619 ns;比较：16;时间/比较：101.19 ns - 带
compareTo的二叉搜索：时间：763 ns;比较：16;时间/比较：47.69 ns
所以，现在我们可以清楚地看到你的问题：compareToIgnoreCase方法花费的时间是equals方法的 16 倍！因为平均而言，需要二叉搜索 16 次比较才能找到给定的单词，因此您可以在这段时间内执行 124 次线性比较。因此，如果您使用比这更短的单词列表进行测试，由于它们使用的方法不同，线性搜索确实总是比二叉搜索更快。
实际上，我还计算了线性搜索能够比二叉搜索更快地找到的单词数：使用compareTo方法时为164，使用compareToIgnoreCase方法时为614。在235882单词列表中，这大约是0.3%。总而言之，我认为可以肯定地说，二叉搜索比线性搜索更快。:)
在你问之前的最后一点：我从binarySearch方法中删除了排序代码，因为这实际上是完全不同的事情。由于您正在比较两种搜索算法，因此如果将排序算法的成本添加到其数字中，则对另一种算法不公平。我已经在另一个答案中发布了以下内容作为评论，但为了完整起见，我将在此处复制它：
二叉搜索增加了排序的开销成本。因此，如果你只需要从数组中查找一个元素，线性搜索总是更快，因为排序至少需要 O(n log n( 时间，然后二叉搜索需要 O(log n( 时间，由 O(n log n( 操作主导。线性搜索在 O(n( 时间内执行，这比 O(n log n( 更好。但是一旦你对数组进行了排序，O(log n(比O(n(好得多。
如果您坚持在 binarySearch 方法中使用排序命令，您应该知道，在我的设置中，从初始随机顺序中排序一长串单词平均需要超过 140000000 ns，即 0.14 秒。在那段时间里，你可以使用 equals 方法执行大约 23000000 次比较，所以你真的不应该使用二叉搜索，如果 a( 你的数组是随机顺序的，b( 如果你只需要从那里找到一个或几个元素。
还有一件事。在此示例中，在 String 数组中搜索单词时，访问数组中项目的开销可以忽略不计，因为数组保存在计算机的快速主内存中。但是，如果你有一大堆有序的文件，并且你试图从中找到一些东西，那么访问单个文件的成本将使所有其他计算的成本可以忽略不计。因此，在这种情况下，二进制搜索也会完全摇滚。
您的基准测试存在缺陷，原因有很多：
- 我们不知道文件的内容。如果搜索的单词在开头，线性搜索将比二叉搜索更快
- 线性搜索与等于比较，而二叉搜索与等于比较忽略大小写
- 执行代码的次数不足以让 JIT 编译代码
我还没有验证你的二叉搜索算法是否正确，但你为什么不使用与JDK捆绑在一起的算法(在java.util.Arrays类中(。
无论如何，您不必测量任何东西。平均而言，二叉搜索比线性搜索快。无需再次证明。
您的代码不会测量二进制搜索，还会在执行搜索之前测量数组的排序。这将始终比简单的线性搜索更长。
} else if (array [midPt].compareToIgnoreCase (word) > 0) {
你根本不需要这个测试。此时，代码中没有其他可能性。它不相等，也不小于：您已经测试过这些;所以它必须大于。
因此，您可以将比较减少 33%。