Searching Algorithms
Searching is a fundamental operation in computer science and programming. It involves finding the location of a specific element in a collection of elements. There are several searching algorithms available, each with its own advantages and disadvantages.
1. Linear Search
Linear search is the simplest searching algorithm. It sequentially checks each element in a collection until the target element is found or the end of the collection is reached. Linear search has a time complexity of O(n), where n is the size of the collection.
Here's an example implementation of linear search in C++:
1#include <iostream>
2#include <vector>
3
4int linearSearch(std::vector<int>& arr, int target) {
5 for (int i = 0; i < arr.size(); ++i) {
6 if (arr[i] == target) {
7 return i;
8 }
9 }
10 return -1;
11}
12
13int main() {
14 std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
15 int target = 6;
16
17 int result = linearSearch(arr, target);
18 if (result != -1) {
19 std::cout << "Element found at index " << result << std::endl;
20 }
21 else {
22 std::cout << "Element not found" << std::endl;
23 }
24
25 return 0;
26}2. Binary Search
Binary search is a more efficient searching algorithm, but it requires the collection to be sorted. It works by repeatedly dividing the collection in half and comparing the middle element with the target element. This process is repeated until the target element is found or the search space is empty. Binary search has a time complexity of O(log n), where n is the size of the collection.
Here's an example implementation of binary search in C++:
1#include <iostream>
2#include <vector>
3
4int binarySearch(std::vector<int>& arr, int target) {
5 int left = 0;
6 int right = arr.size() - 1;
7 while (left <= right) {
8 int mid = left + (right - left) / 2;
9 if (arr[mid] == target) {
10 return mid;
11 }
12 else if (arr[mid] < target) {
13 left = mid + 1;
14 }
15 else {
16 right = mid - 1;
17 }
18 }
19 return -1;
20}
21
22int main() {
23 std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
24 int target = 6;
25
26 int result = binarySearch(arr, target);
27 if (result != -1) {
28 std::cout << "Element found at index " << result << std::endl;
29 }
30 else {
31 std::cout << "Element not found" << std::endl;
32 }
33
34 return 0;
35}xxxxxxxxxx}int linearSearch(std::vector<int>& arr, int target) { for (int i = 0; i < arr.size(); ++i) { if (arr[i] == target) { return i; } } return -1;}int binarySearch(std::vector<int>& 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; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1;}