# So sánh thời gian chạy

So sánh thời gian chạy của thuật toán Linear Search và thuật toán Binary Search
user_1746670
c_cpp
12 days ago
1.4 kB
4
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

int LinearSearch(int a[], int n, int x) {
int i = 0;

while (i < n && a[i] != x) {
i++;
}
if (i < n) return i;

return -1;
}

int BinarySearch_DQ(int a[], int left, int right, int x) {
if (left > right) return -1;

int mid = (left + right) / 2;

if (x == a[mid])
return mid;
else if (x > a[mid])
return BinarySearch_DQ(a, mid + 1, right, x);
else
return BinarySearch_DQ(a, left, mid - 1, x);
}

void PhatSinhMang(int a[], int n) {
srand(0);
for (int i = 0; i < n; i++) {
a[i] = rand() % 10000;
}
}

void PhatSinhMangTang(int a[], int n) {
srand(0);

a[0] = rand() % 50;

for (int i = 1; i < n; i++) {
a[i] = a[i - 1] + rand() % 10;
}
}

int main() {
int ls1[1000];
PhatSinhMang(ls1, 1000);

int bs1[1000];
PhatSinhMangTang(bs1, 1000);

#if 0
clock_t start, end;
start = clock();
LinearSearch(ls1, 1000, 300);
end = clock();
double t = double(end - start) / CLOCKS_PER_SEC;
cout << "Thoi gian tim kiem tuyen tinh la: " << t << " giay" << endl;
#endif

#if 1
clock_t start, end;
start = clock();
BinarySearch_DQ(ls1, 0, 1000, 300);
end = clock();
double t = double(end - start) / CLOCKS_PER_SEC;
cout << "Thoi gian tim kiem nhi phan la: " << t << endl;
#endif

return 0;
}