二分搜索比线性搜索花费更多时间
Binary search taking more time than linear search
我最近在研究二进制和线性搜索，并决定真正检查这两种搜索算法实际花费的时间有什么不同。这是我的代码：
#include <bits/stdc++.h>
using namespace std;
void Print(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
void Merge_sort(int arr[], int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
Merge_sort(arr, start, mid);
Merge_sort(arr, mid + 1, end);
int size = end - start + 1;
int arr_new[size];
int i = start, j = mid + 1;
for (int k = 0; k < size; k++) {
if (i > mid) {
arr_new[k] = arr[j++];
} else if (j > end) {
arr_new[k] = arr[i++];
} else if (arr[i] < arr[j]) {
arr_new[k] = arr[i++];
} else {
arr_new[k] = arr[j++];
}
}
int index = start;
for (int k = 0; k < size; k++) {
arr[index++] = arr_new[k];
}
}
int binary_search(int arr[], int start, int end, int x) {
if (start > end) {
return -1;
}
int mid = (start + end) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binary_search(arr, start, mid - 1, x);
} else {
return binary_search(arr, mid + 1, end, x);
}
}
int linear_search(int arr[], int size, int x) {
for (int i = 0; i < size; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
int main() {
int size;
clock_t start, start1, end, end1;
double time1, time2;
cin >> size;
int *arr1 = new int[size];
int *arr2 = new int[size];
for (int i = 0; i < size; i++) {
int j = rand() % 1000;
arr1[i] = i;
arr2[i] = i;
}
Merge_sort(arr1, 0, size - 1);
start = clock();
cout << binary_search(arr1, 0, size - 1, 15) << endl;
end = clock();
time1 = (double)(end - start) / (double)(CLOCKS_PER_SEC);
cout << "Time taken by binary search is : \t" << fixed
<< time1 << setprecision(8);
cout << " sec " << endl;
start1 = clock();
cout << linear_search(arr2, size, 15) << endl;
end1 = clock();
time2 = (double)(end1 - start1) / (double)(CLOCKS_PER_SEC);
cout << "Time taken by linear search is : \t" << fixed
<< time2 << setprecision(8);
cout << " sec " << endl;
return 0;
}
我在二分查找部分使用了归并排序对数组进行排序，但是在计算耗时时排除了它。
请看一看，告诉我哪里出错了。
正如很多评论中提到的，我添加了一个我在网上获得的结果 IDE。
size = 10000, linear = 0.000005 sec, binary = 0.00005 sec
我刚刚在 YouTube 上观看了一个关于排序的有趣的 CPP Con 视频，其中一部分讨论了线性搜索与二分搜索。
现代 CPU 执行一些非常有趣的预测工作。他们可能会提前猜测，如果您按照他们认为您的代码将采用的路径进行操作，效率会大大提高。二进制搜索使它无法工作，因此它们实际上在旧硬件没有这样做的现代硬件上可能会更慢，因此一旦样本量增长到可能少到一些，二进制搜索通常会快得多20 个值。
https://www.youtube.com/watch?v=FJJTYQYB1JQ&t=2272s
所以在某种程度上，你的样本量很重要，但这次谈话也可能会有所启发。
如果输入量足够大，二分查找确实比线性查找快。当计算机科学家谈论一种算法比另一种算法更快时，他们的意思是一种算法的时间复杂度优于另一种算法。
二分查找的时间复杂度最差 O(lgn)，其中 lgn 表示 n 的基于 2 的对数。
线性搜索的时间复杂度最差 O(n)，其中 n。
在这两种情况下，n 是输入的大小，表示您正在搜索的数字集的大小。
形式上，O(g(n)) 定义为，The set of functions f(n) such that there exists a positive integer n_0 such that for n >= n_0, there exists a constant 0 <= f(n) <= c1*g(n)
撇开所有数学和形式定义不谈，总而言之，从长远来看，二分搜索比线性搜索更好。从长远来看，我的意思是如果您的输入大小足够大。我假设你 运行 程序使用较少的数字，比如 10 或者 100。但是当你有大量数据时，比如 10^5 个数字，那么二进制搜索总是会更快。
此外，在最坏的情况下，一种算法通常比其他算法更好。也就是说，如果您要搜索的数字位于数组的开头，那么您将在第一次尝试时得到该数字。但是对于二分查找，它会花费一些步骤。
对于线性搜索，最坏的情况是您要搜索的数字位于列表的末尾。
所以在最坏情况和平均情况下，二分查找性能更好。
在您的程序中，您使用递归进行二分查找，使用 for 循环进行线性查找。递归比循环有更多的开销。当您使用 @JosephLarson 提到的循环时，编译器会进行一些智能预处理。但是如果你 运行 你的代码输入足够大，我假设你会发现二进制搜索更快。
此外，您可以将二分查找比作查找书中的特定页码。二分查找总是比一次翻一页要快。
题中的代码包含了std::cout输出数据的时间。尝试使用 non-recursive 二进制搜索：
int BinSrc(int a[], int cnt, int x)
{
int lo = 0;
int hi = cnt;
int i = 0;
while((hi - lo) > 1){
i = (lo + hi)/2;
if(x < a[i]){
hi = i;
continue;
}
if(x > a[i]){
lo = i;
continue;
}
break;
}
if(x == a[i])
return i;
return cnt;
}
测试程序
#include <chrono>
#include <iostream>
#include <iomanip>
//----------------------------------------------------------------------//
// BinSrc //
//----------------------------------------------------------------------//
int BinSrc(int a[], int cnt, int x)
{
int lo = 0;
int hi = cnt;
int i = 0;
while((hi - lo) > 1){
i = (lo + hi)/2;
if(x < a[i]){
hi = i;
continue;
}
if(x > a[i]){
lo = i;
continue;
}
break;
}
if(x == a[i])
return i;
return cnt;
}
//----------------------------------------------------------------------//
// LinSrc //
//----------------------------------------------------------------------//
int LinSrc(int a[], int cnt, int x)
{
int i;
for(i = 0; i < cnt; i++)
if(x == a[i])
return i;
return cnt;
}
#define COUNT (10000)
#define GCC 0
int main()
{
int * a = new int [COUNT]; // allocate data array
std::chrono::high_resolution_clock::time_point binbeg, binend, linbeg, linend;
int i, j;
for(int i = 0; i < COUNT; i++)
a[i] = i;
#if GCC
linbeg = std::chrono::_V2::system_clock::now();
i = LinSrc(a, COUNT, COUNT-1);
linend = std::chrono::_V2::system_clock::now();
binbeg = std::chrono::_V2::system_clock::now();
j = BinSrc(a, COUNT, COUNT-1);
binend = std::chrono::_V2::system_clock::now();
#else
linbeg = std::chrono::steady_clock::now();
i = LinSrc(a, COUNT, COUNT-1);
linend = std::chrono::steady_clock::now();
binbeg = std::chrono::steady_clock::now();
j = BinSrc(a, COUNT, COUNT-1);
binend = std::chrono::steady_clock::now();
#endif
std::cout << "Time taken by linear search is : \t" << std::fixed << std::setprecision(8)
<< (std::chrono::duration_cast<std::chrono::nanoseconds>(linend - linbeg).count())/1000000000.;
std::cout << " sec " << std::endl;
std::cout << "Time taken by binary search is : \t" << std::fixed << std::setprecision(8)
<< (std::chrono::duration_cast<std::chrono::nanoseconds>(binend - binbeg).count())/1000000000.;
std::cout << " sec " << std::endl;
delete a;
if(i != j)
std::cout << "error" << std::endl;
return(0);
}
问题非常简单，一个好的 C++ 编译器会立即指出它并具有足够的警告级别：
c++ -O3 -Weverything -o binsearch binsearch.cpp
binsearch.cpp:81:13: warning: unused variable 'j' [-Wunused-variable]
int j = rand() % 1000;
此警告指出 main() 函数中此循环中的一个主要问题：
for (int i = 0; i < size; i++) {
int j = rand() % 1000;
arr1[i] = i;
arr2[i] = i;
}
rand() 未使用，两个数组都初始化为从 0 到 size-1.
的相同单调序列
当您测量找到值 15 所花费的时间时，结果可能有利于线性搜索，因为 15 在两个数组中都出现在第 16 位，非常接近开头，因此在线性搜索中可以非常快速地找到它，并且在 10000 元素排序数组中进行二进制搜索的步骤数大致相同。
问题较多：
您在测量中包括格式化输出所花费的时间，这是不正确的，因为它可能支配基准测试。建议在静音模式下执行所有测量，然后显示结果。
您还应该进行多次搜索：查找出现在数组开头、中间和结尾的数字以及未出现在数组中的数字。
您应该重复搜索以获得更有意义的函数计时 运行 快速因为 clock() 可能具有有限的粒度（OS/X 上为 1 微秒） .
这是一个修改后的版本，具有各种尺寸的基准：
#include <bits/stdc++.h>
using namespace std;
static void Merge_sort(int arr[], int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
Merge_sort(arr, start, mid);
Merge_sort(arr, mid + 1, end);
int size = end - start + 1;
int *arr_new = new int[size];
int i = start, j = mid + 1;
for (int k = 0; k < size; k++) {
if (i > mid) {
arr_new[k] = arr[j++];
} else if (j > end) {
arr_new[k] = arr[i++];
} else if (arr[i] < arr[j]) {
arr_new[k] = arr[i++];
} else {
arr_new[k] = arr[j++];
}
}
int index = start;
for (int k = 0; k < size; k++) {
arr[index++] = arr_new[k];
}
delete[] arr_new;
}
static int binary_search(int arr[], int start, int end, int x) {
if (start > end) {
return -1;
}
int mid = start + (end - start) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binary_search(arr, start, mid - 1, x);
} else {
return binary_search(arr, mid + 1, end, x);
}
}
static int linear_search(int arr[], int size, int x) {
for (int i = 0; i < size; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
static int test(int size) {
int *arr1 = new int[size];
int *arr2 = new int[size];
for (int i = 0; i < size; i++) {
int j = rand();
arr1[i] = j;
arr2[i] = j;
}
Merge_sort(arr1, 0, size - 1);
clock_t start1 = clock();
int index1[4] = {};
for (int i = 0; i < 100; i++) {
index1[0] = binary_search(arr1, 0, size - 1, arr1[0]);
index1[1] = binary_search(arr1, 0, size - 1, arr1[size / 2]);
index1[2] = binary_search(arr1, 0, size - 1, arr1[size - 1]);
index1[3] = binary_search(arr1, 0, size - 1, -1);
}
clock_t end1 = clock();
clock_t start2 = clock();
int index2[4] = {};
for (int i = 0; i < 100; i++) {
index2[0] = linear_search(arr2, size, arr1[0]);
index2[1] = linear_search(arr2, size, arr1[size / 2]);
index2[2] = linear_search(arr2, size, arr1[size - 1]);
index2[3] = linear_search(arr2, size, -1);
}
clock_t end2 = clock();
double time1 = (end1 - start1) * 1000.0 / CLOCKS_PER_SEC;
double time2 = (end2 - start2) * 1000.0 / CLOCKS_PER_SEC;
printf("size=%8d: binary searches: %8.3fms, %d %d %d %d\n",
size, time1, index1[0], index1[1], index1[2], index1[3]);
printf("size=%8d: linear searches: %8.3fms, %d %d %d %d\n",
size, time2, index2[0], index2[1], index2[2], index2[3]);
delete[] arr1;
delete[] arr2;
return 0;
}
int main() {
for (int size = 1; size <= 10000000; size *= 10) {
test(size);
}
return 0;
}
输出：
size= 1: binary searches: 0.002ms, 0 0 0 -1
size= 1: linear searches: 0.000ms, 0 0 0 -1
size= 2: binary searches: 0.002ms, 0 1 1 -1
size= 2: linear searches: 0.002ms, 0 1 1 -1
size= 5: binary searches: 0.002ms, 0 2 4 -1
size= 5: linear searches: 0.002ms, 3 0 4 -1
size= 10: binary searches: 0.003ms, 0 5 9 -1
size= 10: linear searches: 0.003ms, 9 7 1 -1
size= 20: binary searches: 0.004ms, 0 10 19 -1
size= 20: linear searches: 0.004ms, 15 18 5 -1
size= 50: binary searches: 0.004ms, 0 25 49 -1
size= 50: linear searches: 0.005ms, 44 24 0 -1
size= 100: binary searches: 0.006ms, 0 50 99 -1
size= 100: linear searches: 0.012ms, 34 91 0 -1
size= 200: binary searches: 0.006ms, 0 100 199 -1
size= 200: linear searches: 0.022ms, 62 123 58 -1
size= 500: binary searches: 0.006ms, 0 250 499 -1
size= 500: linear searches: 0.050ms, 47 389 252 -1
size= 1000: binary searches: 0.006ms, 0 500 999 -1
size= 1000: linear searches: 0.121ms, 902 808 422 -1
size= 2000: binary searches: 0.008ms, 0 1000 1999 -1
size= 2000: linear searches: 0.369ms, 733 1992 1866 -1
size= 5000: binary searches: 0.010ms, 0 2500 4999 -1
size= 5000: linear searches: 0.656ms, 2635 4605 1819 -1
size= 10000: binary searches: 0.015ms, 0 5000 9999 -1
size= 10000: linear searches: 1.137ms, 6722 8419 5128 -1
size= 20000: binary searches: 0.012ms, 0 10000 19999 -1
size= 20000: linear searches: 2.265ms, 16893 6637 10738 -1
size= 50000: binary searches: 0.013ms, 0 25000 49999 -1
size= 50000: linear searches: 4.538ms, 19705 40371 9661 -1
size= 100000: binary searches: 0.014ms, 0 50000 99999 -1
size= 100000: linear searches: 8.565ms, 42378 57447 33679 -1
size= 200000: binary searches: 0.020ms, 0 100000 199999 -1
size= 200000: linear searches: 26.003ms, 14037 198103 158988 -1
size= 500000: binary searches: 0.016ms, 0 250000 499999 -1
size= 500000: linear searches: 33.657ms, 162357 162899 18194 -1
如您所见，对于大尺寸的一般情况，二分搜索要快得多，但线性搜索要简单得多，并且对于最多 20 个元素具有更快或等效的计时。 binary_search 的非递归版本可能会稍微降低阈值。但是请注意，您对 binary_search 的实现并不总是 return 第一次出现的索引，以防重复。
我最近在研究二进制和线性搜索，并决定真正检查这两种搜索算法实际花费的时间有什么不同。这是我的代码：
#include <bits/stdc++.h>
using namespace std;
void Print(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
void Merge_sort(int arr[], int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
Merge_sort(arr, start, mid);
Merge_sort(arr, mid + 1, end);
int size = end - start + 1;
int arr_new[size];
int i = start, j = mid + 1;
for (int k = 0; k < size; k++) {
if (i > mid) {
arr_new[k] = arr[j++];
} else if (j > end) {
arr_new[k] = arr[i++];
} else if (arr[i] < arr[j]) {
arr_new[k] = arr[i++];
} else {
arr_new[k] = arr[j++];
}
}
int index = start;
for (int k = 0; k < size; k++) {
arr[index++] = arr_new[k];
}
}
int binary_search(int arr[], int start, int end, int x) {
if (start > end) {
return -1;
}
int mid = (start + end) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binary_search(arr, start, mid - 1, x);
} else {
return binary_search(arr, mid + 1, end, x);
}
}
int linear_search(int arr[], int size, int x) {
for (int i = 0; i < size; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
int main() {
int size;
clock_t start, start1, end, end1;
double time1, time2;
cin >> size;
int *arr1 = new int[size];
int *arr2 = new int[size];
for (int i = 0; i < size; i++) {
int j = rand() % 1000;
arr1[i] = i;
arr2[i] = i;
}
Merge_sort(arr1, 0, size - 1);
start = clock();
cout << binary_search(arr1, 0, size - 1, 15) << endl;
end = clock();
time1 = (double)(end - start) / (double)(CLOCKS_PER_SEC);
cout << "Time taken by binary search is : \t" << fixed
<< time1 << setprecision(8);
cout << " sec " << endl;
start1 = clock();
cout << linear_search(arr2, size, 15) << endl;
end1 = clock();
time2 = (double)(end1 - start1) / (double)(CLOCKS_PER_SEC);
cout << "Time taken by linear search is : \t" << fixed
<< time2 << setprecision(8);
cout << " sec " << endl;
return 0;
}
我在二分查找部分使用了归并排序对数组进行排序，但是在计算耗时时排除了它。 请看一看，告诉我哪里出错了。 正如很多评论中提到的，我添加了一个我在网上获得的结果 IDE。
size = 10000, linear = 0.000005 sec, binary = 0.00005 sec
我刚刚在 YouTube 上观看了一个关于排序的有趣的 CPP Con 视频，其中一部分讨论了线性搜索与二分搜索。
现代 CPU 执行一些非常有趣的预测工作。他们可能会提前猜测，如果您按照他们认为您的代码将采用的路径进行操作，效率会大大提高。二进制搜索使它无法工作，因此它们实际上在旧硬件没有这样做的现代硬件上可能会更慢，因此一旦样本量增长到可能少到一些，二进制搜索通常会快得多20 个值。
https://www.youtube.com/watch?v=FJJTYQYB1JQ&t=2272s
所以在某种程度上，你的样本量很重要，但这次谈话也可能会有所启发。
如果输入量足够大，二分查找确实比线性查找快。当计算机科学家谈论一种算法比另一种算法更快时，他们的意思是一种算法的时间复杂度优于另一种算法。
二分查找的时间复杂度最差 O(lgn)，其中 lgn 表示 n 的基于 2 的对数。
线性搜索的时间复杂度最差 O(n)，其中 n。
在这两种情况下，n 是输入的大小，表示您正在搜索的数字集的大小。
形式上，O(g(n)) 定义为，The set of functions f(n) such that there exists a positive integer n_0 such that for n >= n_0, there exists a constant 0 <= f(n) <= c1*g(n)
撇开所有数学和形式定义不谈，总而言之，从长远来看，二分搜索比线性搜索更好。从长远来看，我的意思是如果您的输入大小足够大。我假设你 运行 程序使用较少的数字，比如 10 或者 100。但是当你有大量数据时，比如 10^5 个数字，那么二进制搜索总是会更快。
此外，在最坏的情况下，一种算法通常比其他算法更好。也就是说，如果您要搜索的数字位于数组的开头，那么您将在第一次尝试时得到该数字。但是对于二分查找，它会花费一些步骤。
对于线性搜索，最坏的情况是您要搜索的数字位于列表的末尾。
所以在最坏情况和平均情况下，二分查找性能更好。
在您的程序中，您使用递归进行二分查找，使用 for 循环进行线性查找。递归比循环有更多的开销。当您使用 @JosephLarson 提到的循环时，编译器会进行一些智能预处理。但是如果你 运行 你的代码输入足够大，我假设你会发现二进制搜索更快。
此外，您可以将二分查找比作查找书中的特定页码。二分查找总是比一次翻一页要快。
题中的代码包含了std::cout输出数据的时间。尝试使用 non-recursive 二进制搜索：
int BinSrc(int a[], int cnt, int x)
{
int lo = 0;
int hi = cnt;
int i = 0;
while((hi - lo) > 1){
i = (lo + hi)/2;
if(x < a[i]){
hi = i;
continue;
}
if(x > a[i]){
lo = i;
continue;
}
break;
}
if(x == a[i])
return i;
return cnt;
}
测试程序
#include <chrono>
#include <iostream>
#include <iomanip>
//----------------------------------------------------------------------//
// BinSrc //
//----------------------------------------------------------------------//
int BinSrc(int a[], int cnt, int x)
{
int lo = 0;
int hi = cnt;
int i = 0;
while((hi - lo) > 1){
i = (lo + hi)/2;
if(x < a[i]){
hi = i;
continue;
}
if(x > a[i]){
lo = i;
continue;
}
break;
}
if(x == a[i])
return i;
return cnt;
}
//----------------------------------------------------------------------//
// LinSrc //
//----------------------------------------------------------------------//
int LinSrc(int a[], int cnt, int x)
{
int i;
for(i = 0; i < cnt; i++)
if(x == a[i])
return i;
return cnt;
}
#define COUNT (10000)
#define GCC 0
int main()
{
int * a = new int [COUNT]; // allocate data array
std::chrono::high_resolution_clock::time_point binbeg, binend, linbeg, linend;
int i, j;
for(int i = 0; i < COUNT; i++)
a[i] = i;
#if GCC
linbeg = std::chrono::_V2::system_clock::now();
i = LinSrc(a, COUNT, COUNT-1);
linend = std::chrono::_V2::system_clock::now();
binbeg = std::chrono::_V2::system_clock::now();
j = BinSrc(a, COUNT, COUNT-1);
binend = std::chrono::_V2::system_clock::now();
#else
linbeg = std::chrono::steady_clock::now();
i = LinSrc(a, COUNT, COUNT-1);
linend = std::chrono::steady_clock::now();
binbeg = std::chrono::steady_clock::now();
j = BinSrc(a, COUNT, COUNT-1);
binend = std::chrono::steady_clock::now();
#endif
std::cout << "Time taken by linear search is : \t" << std::fixed << std::setprecision(8)
<< (std::chrono::duration_cast<std::chrono::nanoseconds>(linend - linbeg).count())/1000000000.;
std::cout << " sec " << std::endl;
std::cout << "Time taken by binary search is : \t" << std::fixed << std::setprecision(8)
<< (std::chrono::duration_cast<std::chrono::nanoseconds>(binend - binbeg).count())/1000000000.;
std::cout << " sec " << std::endl;
delete a;
if(i != j)
std::cout << "error" << std::endl;
return(0);
}
问题非常简单，一个好的 C++ 编译器会立即指出它并具有足够的警告级别：
c++ -O3 -Weverything -o binsearch binsearch.cpp
binsearch.cpp:81:13: warning: unused variable 'j' [-Wunused-variable]
int j = rand() % 1000;
此警告指出 main() 函数中此循环中的一个主要问题：
for (int i = 0; i < size; i++) {
int j = rand() % 1000;
arr1[i] = i;
arr2[i] = i;
}
rand() 未使用，两个数组都初始化为从 0 到 size-1.
当您测量找到值 15 所花费的时间时，结果可能有利于线性搜索，因为 15 在两个数组中都出现在第 16 位，非常接近开头，因此在线性搜索中可以非常快速地找到它，并且在 10000 元素排序数组中进行二进制搜索的步骤数大致相同。
问题较多：
您在测量中包括格式化输出所花费的时间，这是不正确的，因为它可能支配基准测试。建议在静音模式下执行所有测量，然后显示结果。
您还应该进行多次搜索：查找出现在数组开头、中间和结尾的数字以及未出现在数组中的数字。
您应该重复搜索以获得更有意义的函数计时 运行 快速因为
clock()可能具有有限的粒度（OS/X 上为 1 微秒） .
这是一个修改后的版本，具有各种尺寸的基准：
#include <bits/stdc++.h>
using namespace std;
static void Merge_sort(int arr[], int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
Merge_sort(arr, start, mid);
Merge_sort(arr, mid + 1, end);
int size = end - start + 1;
int *arr_new = new int[size];
int i = start, j = mid + 1;
for (int k = 0; k < size; k++) {
if (i > mid) {
arr_new[k] = arr[j++];
} else if (j > end) {
arr_new[k] = arr[i++];
} else if (arr[i] < arr[j]) {
arr_new[k] = arr[i++];
} else {
arr_new[k] = arr[j++];
}
}
int index = start;
for (int k = 0; k < size; k++) {
arr[index++] = arr_new[k];
}
delete[] arr_new;
}
static int binary_search(int arr[], int start, int end, int x) {
if (start > end) {
return -1;
}
int mid = start + (end - start) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binary_search(arr, start, mid - 1, x);
} else {
return binary_search(arr, mid + 1, end, x);
}
}
static int linear_search(int arr[], int size, int x) {
for (int i = 0; i < size; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
static int test(int size) {
int *arr1 = new int[size];
int *arr2 = new int[size];
for (int i = 0; i < size; i++) {
int j = rand();
arr1[i] = j;
arr2[i] = j;
}
Merge_sort(arr1, 0, size - 1);
clock_t start1 = clock();
int index1[4] = {};
for (int i = 0; i < 100; i++) {
index1[0] = binary_search(arr1, 0, size - 1, arr1[0]);
index1[1] = binary_search(arr1, 0, size - 1, arr1[size / 2]);
index1[2] = binary_search(arr1, 0, size - 1, arr1[size - 1]);
index1[3] = binary_search(arr1, 0, size - 1, -1);
}
clock_t end1 = clock();
clock_t start2 = clock();
int index2[4] = {};
for (int i = 0; i < 100; i++) {
index2[0] = linear_search(arr2, size, arr1[0]);
index2[1] = linear_search(arr2, size, arr1[size / 2]);
index2[2] = linear_search(arr2, size, arr1[size - 1]);
index2[3] = linear_search(arr2, size, -1);
}
clock_t end2 = clock();
double time1 = (end1 - start1) * 1000.0 / CLOCKS_PER_SEC;
double time2 = (end2 - start2) * 1000.0 / CLOCKS_PER_SEC;
printf("size=%8d: binary searches: %8.3fms, %d %d %d %d\n",
size, time1, index1[0], index1[1], index1[2], index1[3]);
printf("size=%8d: linear searches: %8.3fms, %d %d %d %d\n",
size, time2, index2[0], index2[1], index2[2], index2[3]);
delete[] arr1;
delete[] arr2;
return 0;
}
int main() {
for (int size = 1; size <= 10000000; size *= 10) {
test(size);
}
return 0;
}
输出：
size= 1: binary searches: 0.002ms, 0 0 0 -1
size= 1: linear searches: 0.000ms, 0 0 0 -1
size= 2: binary searches: 0.002ms, 0 1 1 -1
size= 2: linear searches: 0.002ms, 0 1 1 -1
size= 5: binary searches: 0.002ms, 0 2 4 -1
size= 5: linear searches: 0.002ms, 3 0 4 -1
size= 10: binary searches: 0.003ms, 0 5 9 -1
size= 10: linear searches: 0.003ms, 9 7 1 -1
size= 20: binary searches: 0.004ms, 0 10 19 -1
size= 20: linear searches: 0.004ms, 15 18 5 -1
size= 50: binary searches: 0.004ms, 0 25 49 -1
size= 50: linear searches: 0.005ms, 44 24 0 -1
size= 100: binary searches: 0.006ms, 0 50 99 -1
size= 100: linear searches: 0.012ms, 34 91 0 -1
size= 200: binary searches: 0.006ms, 0 100 199 -1
size= 200: linear searches: 0.022ms, 62 123 58 -1
size= 500: binary searches: 0.006ms, 0 250 499 -1
size= 500: linear searches: 0.050ms, 47 389 252 -1
size= 1000: binary searches: 0.006ms, 0 500 999 -1
size= 1000: linear searches: 0.121ms, 902 808 422 -1
size= 2000: binary searches: 0.008ms, 0 1000 1999 -1
size= 2000: linear searches: 0.369ms, 733 1992 1866 -1
size= 5000: binary searches: 0.010ms, 0 2500 4999 -1
size= 5000: linear searches: 0.656ms, 2635 4605 1819 -1
size= 10000: binary searches: 0.015ms, 0 5000 9999 -1
size= 10000: linear searches: 1.137ms, 6722 8419 5128 -1
size= 20000: binary searches: 0.012ms, 0 10000 19999 -1
size= 20000: linear searches: 2.265ms, 16893 6637 10738 -1
size= 50000: binary searches: 0.013ms, 0 25000 49999 -1
size= 50000: linear searches: 4.538ms, 19705 40371 9661 -1
size= 100000: binary searches: 0.014ms, 0 50000 99999 -1
size= 100000: linear searches: 8.565ms, 42378 57447 33679 -1
size= 200000: binary searches: 0.020ms, 0 100000 199999 -1
size= 200000: linear searches: 26.003ms, 14037 198103 158988 -1
size= 500000: binary searches: 0.016ms, 0 250000 499999 -1
size= 500000: linear searches: 33.657ms, 162357 162899 18194 -1
如您所见，对于大尺寸的一般情况，二分搜索要快得多，但线性搜索要简单得多，并且对于最多 20 个元素具有更快或等效的计时。 binary_search 的非递归版本可能会稍微降低阈值。但是请注意，您对 binary_search 的实现并不总是 return 第一次出现的索引，以防重复。