|
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 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function for Linear Search int linearSearch(const vector<int>& arr, int target) { for (size_t i = 0; i < arr.size(); ++i) { if (arr[i] == target) { return i; // Return the index where target is found } } return -1; // Return -1 if target is not found } // Function for Binary Search int binarySearch(const 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; // Return the index where target is found } if (arr[mid] < target) { left = mid + 1; // Search in the right half } else { right = mid - 1; // Search in the left half } } return -1; // Return -1 if target is not found } int main() { vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; // Sorted array for binary search int target, index; cout << "Enter the number to search: "; cin >> target; // Linear Search index = linearSearch(arr, target); if (index != -1) { cout << "Linear Search: Found " << target << " at index " << index << endl; } else { cout << "Linear Search: " << target << " not found" << endl; } // Binary Search index = binarySearch(arr, target); if (index != -1) { cout << "Binary Search: Found " << target << " at index " << index << endl; } else { cout << "Binary Search: " << target << " not found" << endl; } return 0; } |
Explanation
- Linear Search:
linearSearch(const vector<int>& arr, int target): This function iterates through each element in the array to find the target value.- Parameters:
arr: The array in which to search.target: The value to search for.
- Logic: It checks each element until it finds the target or reaches the end of the array.
- Return: Returns the index of the target if found; otherwise, returns
-1.
- Parameters:
- Binary Search:
binarySearch(const vector<int>& arr, int target): This function performs a binary search on a sorted array to find the target value.- Parameters:
arr: The sorted array in which to search.target: The value to search for.
- Logic: It repeatedly divides the search interval in half, comparing the target value with the middle element until the target is found or the interval is empty.
- Return: Returns the index of the target if found; otherwise, returns
-1.
- Parameters:
- Main Function:
- Initializes a sorted array
arrand prompts the user to enter a number to search for. - Calls both
linearSearch()andbinarySearch()functions with the entered number. - Displays the results of both searches.
- Initializes a sorted array
Notes:
- Linear Search is simple and works for unsorted arrays but is less efficient (O(n) time complexity).
- Binary Search is efficient for sorted arrays with a time complexity of O(log n), but requires the array to be sorted.