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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
#ifndef SEARCH_FUNCTIONS
#define SEARCH_FUNCTIONS
#include <vector>
#include <list>
using namespace std;
// perform a sequential search of an integer array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
int seqSearch(const int arr[], int first, int last, int target);
// perform asequential search for a target in the index range
// [first, last). return the index of a match or last if the
// target is not in arr
template <typename T>
int seqSearch(const T arr[], int first, int last, const T& target);
// perform a binary search of an integer array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
int binSearch(const int arr[], int first, int last, int target);
// perform a binary search of an array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
template <typename T>
int binSearch(const T arr[], int first, int last, const T& target);
// vector version of the sequential search
template <typename T>
int seqSearch(const vector<T>& v, int first, int last, const T& target);
// vector version of the binary search
template <typename T>
int binSearch(const vector<T>& v, int first, int last, const T& target);
// perform the sequential search for target in the list
// iterator range [first, last). return an iterator pointing
// at the target in the list or last if target is not found
template <typename T>
list<T>::iterator seqSearch(list<T>::iterator first,
list<T>::iterator last, const T& target);
// perform the sequential search for target in the container
// iterator range [first, last). return an iterator pointing
// at the target in the container or last if target is not
// found
template <typename Iterator, typename T>
Iterator find(Iterator first, Iterator last, const T& target);
// ***********************************************************
// search function implementations
// ***********************************************************
int seqSearch(const int arr[], int first, int last, int target)
{
int i;
// scan indices in the range first <= i < last
for(i=first; i < last; i++)
if (arr[i] == target)
return i; // immediately return on a match
return last; // return last if target not found
}
template <typename T>
int seqSearch(const T arr[], int first, int last, const T& target)
{
int i;
// scan indices in the range first <= i < last
for(i=first; i < last; i++)
if (arr[i] == target) // assume T has the "==" operator
return i; // immediately return on a match
return last; // return last if target not found
}
int binSearch(const int arr[], int first, int last, int target)
{
int mid; // index of the midpoint
int midValue; // object that is assigned arr[mid]
int origLast = last; // save original value of last
while (first < last) // test for nonempty sublist
{
mid = (first+last)/2;
midValue = arr[mid];
if (target == midValue)
return mid; // have a match
// determine which sublist to search
else if (target < midValue)
last = mid; // search lower sublist. reset last
else
first = mid+1; // search upper sublist. reset first
}
return origLast; // target not found
}
template <typename T>
int binSearch(const T arr[], int first, int last, const T& target)
{
int mid; // index of the midpoint
T midValue; // object that is assigned arr[mid]
int origLast = last; // save original value of last
while (first < last) // test for nonempty sublist
{
mid = (first+last)/2;
midValue = arr[mid];
if (target == midValue)
return mid; // have a match
// determine which sublist to search
else if (target < midValue)
last = mid; // search lower sublist. reset last
else
first = mid+1; // search upper sublist. reset first
}
return origLast; // target not found
}
template <typename T>
int seqSearch(const vector<T>& v, int first, int last, const T& target)
{
int i;
// scan indices in the range first <= i < last
for(i=first; i < last; i++)
if (v[i] == target) // assume T has the "==" operator
return i; // immediately return on a match
return last; // otherwise return last
}
template <typename T>
int binSearch(const vector<T>& v, int first, int last, const T& target)
{
int mid; // index of the midpoint
T midvalue; // object that is assigned v[mid]
int origLast = last; // save original value of last
while (first < last) // test for nonempty sublist
{
mid = (first+last)/2;
midvalue = v[mid];
if (target == midvalue)
return mid; // have a match
// determine which sublist to search
else if (target < midvalue)
last = mid; // search lower sublist. reset last
else
first = mid+1; // search upper sublist. reset first
}
return origLast; // target not found
}
template <typename T>
list<T>::iterator seqSearch(list<T>::iterator first,
list<T>::iterator last, const T& target)
{
// start at location first
list<T>::iterator iter = first;
// compare list elements with item until either
// we arrive at last or locate item
while(iter != last && !(*iter == target))
iter++;
// iter either points at item or is last
return iter;
}
template <typename Iterator, typename T>
Iterator find(Iterator first, Iterator last, const T& target)
{
Iterator iter = first;
// scan iterator range [first, last), stopping
// if the loop locates target
while (iter != last && *iter != target)
iter++;
// if target located, iter points at it; otherwise
// is has value last
return iter;
}
#endif // SEARCH_FUNCTIONS
| |
