Searching algorithms in C++ are essential techniques used to locate elements within a collection of data. The choice of searching algorithm depends on factors such as the size of the dataset, whether the data is sorted, and the expected frequency of searches. Here's an overview of some common searching algorithms and their implementations in C++:
Linear search is a straightforward searching algorithm that sequentially checks each element in the list until the desired element is found or the end of the list is reached.
#include
#include
int linearSearch(const std::vector& arr, int target) {
for (int i = 0; i < arr.size(); ++i) {
if (arr[i] == target) {
return i; // Return index of target if found
}
}
return -1; // Return -1 if target is not found
}
int main() {
std::vector nums = {10, 20, 30, 40, 50};
int target = 30;
int index = linearSearch(nums, target);
if (index != -1) {
std::cout << "Element found at index " << index << std::endl;
} else {
std::cout << "Element not found" << std::endl;
}
return 0;
}
Binary search is a more efficient searching algorithm applicable to sorted arrays. It repeatedly divides the search interval in half until the target element is found or the interval is empty.
#include
#include
int binarySearch(const std::vector& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Return index of target if found
} else if (arr[mid] < target) {
left = mid + 1; // Target is in the right half
} else {
right = mid - 1; // Target is in the left half
}
}
return -1; // Return -1 if target is not found
}
int main() {
std::vector nums = {10, 20, 30, 40, 50};
int target = 30;
int index = binarySearch(nums, target);
if (index != -1) {
std::cout << "Element found at index " << index << std::endl;
} else {
std::cout << "Element not found" << std::endl;
}
return 0;
}
Jump search is an algorithm for searching sorted arrays by jumping ahead by fixed steps and then performing linear search between the jumps.
#include
#include
#include
int jumpSearch(const std::vector& arr, int target) {
int n = arr.size();
int step = std::sqrt(n);
int prev = 0;
while (arr[std::min(step, n) - 1] < target) {
prev = step;
step += std::sqrt(n);
if (prev >= n) {
return -1; // Element not present
}
}
while (arr[prev] < target) {
prev++;
if (prev == std::min(step, n)) {
return -1; // Element not present
}
}
if (arr[prev] == target) {
return prev; // Return index if target is found
}
return -1; // Return -1 if target is not found
}
int main() {
std::vector nums = {10, 20, 30, 40, 50};
int target = 30;
int index = jumpSearch(nums, target);
if (index != -1) {
std::cout << "Element found at index " << index << std::endl;
} else {
std::cout << "Element not found" << std::endl;
}
return 0;
}
Interpolation search is an improved variant of binary search that works better for uniformly distributed data by calculating the position of the target element based on the value of the key and the distribution of elements.
#include
#include
int interpolationSearch(const std::vector& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right && target >= arr[left] && target <= arr[right]) {
if (left == right) {
if (arr[left] == target) {
return left;
}
return -1; // Element not found
}
int pos = left + ((double)(right - left) / (arr[right] - arr[left])) * (target - arr[left]);
if (arr[pos] == target) {
return pos; // Return index if target is found
}
if (arr[pos] < target) {
left = pos + 1; // Target is in the right half
} else {
right = pos - 1; // Target is in the left half
}
}
return -1; // Return -1 if target is not found
}
int main() {
std::vector nums = {10, 20, 30, 40, 50};
int target = 30;
int index = interpolationSearch(nums, target);
if (index != -1) {
std::cout << "Element found at index " << index << std::endl;
} else {
std::cout << "Element not found" << std::endl;
}
return 0;
}