Linear Search is a searching algorithm that is also known as a sequential search. It is one of the very popular searching algorithms that is used to search whether an element is present in the given array or not.
Problem: Given an array of integers arr[ ] of size n and a target element x, write a C++ program to search the position of x in the given array. You can return -1 in the element x is not present in the given array.Input arr[ ] = {20, 10, 7, 30, 11, 15, 36} x = 11 Output: 4 Element is present at index 4 Input arr[ ] = {5, 10, 8, 30, 12, 70, 25, 19} x = 15 Output: -1 Element is not present at any index.
Steps to follow:
- Start from the 0 index element of the given array and start comparing each element with x.
- If you find an index element matches with x, return the index. arr[index] == x
- If you are unable to find the matching element in the array, return -1.
Example: C++ Program for Linear search.
#include <iostream> using namespace std; // Function for Linear Search int linearSearch(int arr[], int n, int x) { int i; for (i = 0; i < n; i++) { if (arr[i] == x) { return i; } } return -1; } int main() { // Elements present in the array int arr[] = {20, 10, 7, 30, 11, 15, 36}; // size of given array int size = sizeof(arr) / sizeof(arr[0]); // Element x to be search in the array int x = 11; int pos = linearSearch(arr, size, x); if (pos == -1) { cout << "Element " << x << " is not present in the given array." << endl; } else { cout << "Element " << x << " is present at index " << pos << endl; } }
Output:
Element 11 is present at index 4
- Time Complexity: O(n).
- Space Complexity: O(1).
Mostly in real-life applications, we rarely use a Linear search algorithm. We mostly use a Binary search algorithm with time complexity O(log n) which is more efficient than this linear search.
No comments:
Post a Comment