Search in c++ language
Searching a vector for a particular element is a common activity. We will consider the two most common search strategies: linear search and binary search.
Linear Search
uses a function named locate that returns the position of the first occurrence of a given element in a vector of integers; if the element is not present, the function returns −1.
#include <iostream>
#include <vector>
#include <iomanip>
int locate(const std::vector < int > & a, int seek) {
int n = a.size();
for (int i = 0; i < n; i++)
if (a[i] == seek)
return i; // Return position immediately
return -1; // Element not found
}
/*
* format(i)
* Prints integer i right justified in a 4-space
* field. Prints "****" if i > 9,999.
*/
void format(int i) {
if (i > 9999)
std::cout << "****" << '\n'; // Too big!
else
std::cout << std::setw(4) << i;
}
/*
* print(v)
* Prints the contents of an int vector.
* v is the vector to print.
*/
void print(const std::vector < int > & v) {
for (int i: v)
format(i);
}
/*
* display(a, value)
* Draws an ASCII art arrow showing where
* the given value is within the vector.
* a is the vector.
* value is the element to locate.
*/
void display(const std::vector < int > & a, int value) {
int position = locate(a, value);
if (position >= 0) {
print(a); // Print contents of the vector
std::cout << '\n';
position = 4 * position + 7; // Compute spacing for arrow
std::cout << std::setw(position);
std::cout << " ^ " << '\n';
std::cout << std::setw(position);
std::cout << " | " << '\n';
std::cout << std::setw(position);
std::cout << " +-- " << value << '\n';
} else {
std::cout << value << " not in ";
print(a);
std::cout << '\n';
}
std::cout << "======" << '\n';
}
int main() {
std::vector < int > list{ 100, 44, 2, 80, 5, 13, 11, 2, 110 };
display(list, 13);
display(list, 2);
display(list, 7);
display(list, 100);
display(list, 110);
}100 44 2 80 5 13 11 2 110
^
|
+-- 13
======
100 44 2 80 5 13 11 2 110
^
|
+-- 2
======
7 not in 100 44 2 80 5 13 11 2 110
======
100 44 2 80 5 13 11 2 110
^
|
+-- 100
======
100 44 2 80 5 13 11 2 110
^
|
+-- 110Binary Search
#include <iostream>
#include <vector>
#include <iomanip>
/*
* binary_search(a, seek)
* Returns the index of element seek in vector a;
* returns -1 if seek is not an element of a
* a is the vector to search; a's contents must be
* sorted in ascending order.
* seek is the element to find.
*/
int binary_search(const std::vector < int > & a, int seek) {
int first = 0, // Initially the first position
last = a.size() - 1, // Initially the last position
mid; // The middle of the vector
while (first <= last) {
mid = first + (last - first + 1) / 2;
if (a[mid] == seek)
return mid; // Found it
else if (a[mid] > seek)
last = mid - 1; // continue with 1st half
else // a[mid] < seek
first = mid + 1; // continue with 2nd half
}
return -1; // Not there
}
/*
* format(i)
* Prints integer i right justified in a 4-space
* field. Prints "****" if i > 9,999.
*/
void format(int i) {
if (i > 9999)
std::cout << "****\n"; // Too big!
else
std::cout << std::setw(4) << i;
}
/*
* print(v)
* Prints the contents of an int vector.
* v is the vector to print.
*/
void print(const std::vector < int > & v) {
for (int i: v)
format(i);
}
/*
* display(a, value)
* Draws an ASCII art arrow showing where
* the given value is within the vector.
* a is the vector.
* value is the element to locate.
*/
void display(const std::vector < int > & a, int value) {
int position = binary_search(a, value);
if (position >= 0) {
print(a); // Print contents of the vector
std::cout << '\n';
position = 4 * position + 7; // Compute spacing for arrow
std::cout << std::setw(position);
std::cout << " ^ " << '\n';
std::cout << std::setw(position);
std::cout << " | " << '\n';
std::cout << std::setw(position);
std::cout << " +-- " << value << '\n';
} else {
std::cout << value << " not in ";
print(a);
std::cout << '\n';
}
std::cout << "======" << '\n';
}
int main() {
// Check binary search on even- and odd-length vectors and
// an empty vector
std::vector < int > even_list{ 1, 2, 3, 4, 5, 6, 7, 8 },
odd_list{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
empty_list;
empty_list;
for (int i = -1; i <= 10; i++)
display(even_list, i);
for (int i = -1; i <= 10; i++)
display(odd_list, i);
for (int i = -1; i <= 10; i++)
display(empty_list, i);
}int first = 0, // Initially the first position
last = a.size() - 1, // Initially the last positionensure that first is less than or equal to last for a nonempty vector. If the vector is empty, first is zero, and last is equal to n − 1 which equals −1. So in the case of an empty vector binary_search will skip the loop body and immediately return −1. This is correct behavior because an empty vector cannot possibly contain any item we seek.
mid = first + (last - first + 1)/2;The problem with this method of computing the midpoint is it fails to produce the correct results more times than The problem arises if the vector is large, and first and last both have relatively large values. The expression first + last can overflow the range of integers producing a meaningless result.
// This version requires vector a to be sorted in
// ascending order.
int linear_search(const std::vector<int>& a, int seek) {
int n = a.size();
for (int i = 0; i < n && a[i] <= seek; i++)
if (a[i] == seek)
return i; // Return position immediately
return -1; // Element not found
}Notice that, as in the original version of linear search, the loop will terminate when all the elements have been examined, but it also will terminate early when it encounters an element larger than the sought element. Since the vector is sorted, there is no need to continue the search once you have begun seeing elements larger than your sought value; seek cannot appear after a larger element in a sorted vector.
