1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include <iostream>
using namespace std;
void getValue(int&);
int linearSearch(int[], int, int, int&);
int binarySearch(int[], int, int, int&);
int main()
{
const int SIZE = 10;
int Array[SIZE] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int LinBMark = 0,
BinBMark = 0,
value,
getValue(value);
LinResults = linearSearch(Array, SIZE, value, LinBMark);
BinResults = binarySearch(Array, SIZE, value, BinBMark);
cout << "Number of comparisons made before finding the value: "
<< value << endl;
cout << "The linear search algorithm: " << LinBMark
<< endl;
cout << "The binary search algorithm: " << BinBMark
<< endl;
return 0;
}
void getValue(int &value)
{
cout << "Enter a value to search for: ";
cin >> value;
}
int linearSearch(int list[], int size, int value, int &LinBMark)
{
int index = 0;
int position = -1;
bool found = false;
while(index < size && !found)
{
if (list[index] == value)
{
found = true;
position = index;
}
index++;
if (position == -1)
LinBMark++;
}
while (LinBMark < 0 || LinBMark > 100)
{
cout << "This integer is not in your array, please enter an integer between 0 and 100: ";
cin >> LinBMark;
return position;
}
int binarySearch(int array[], int size, int value, int &BinBMark);
{
int first = 0,
last = size - 1,
middle,
position = -1;
bool found = false;
while (!found && first <= last)
{
middle = (first + last) / 2;
if (array[middle] = value)
{
found = true;
position = middle;
}
else if (array[middle] > value)
last = middle - 1;
else
first = middle + 1;
if (position == -1)
LinBMark++;
}
return position;
}
}
|
