{"id":81396,"date":"2021-06-29T09:00:56","date_gmt":"2021-06-29T03:30:56","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=81396"},"modified":"2021-06-29T09:00:56","modified_gmt":"2021-06-29T03:30:56","slug":"linear-search-in-data-structure","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/","title":{"rendered":"Linear Search in Data Structure"},"content":{"rendered":"

Searching is a technique used to find out a particular element from a given list of elements. We can perform searching on any data structure such as arrays, linked lists, trees, graphs, etc.<\/p>\n

If the element we are searching for is present in the list\/data structure, the searching technique returns success. Otherwise, the search is considered unsuccessful.<\/p>\n

There are three popular search methods:
\n1. Linear search
\n2. Binary search
\n3. Interpolation search<\/p>\n

Out of these searching techniques, the first two are more popular and widely used. Let us discuss one of them in this article.<\/p>\n

Linear Search<\/h3>\n

It is also known as sequential search. As the name suggests, in linear search, we sequentially traverse all the elements.<\/p>\n

If we can find the element we were searching for, the linear search algorithm returns the address\/location of that element in the list. Otherwise, the algorithm returns NULL. We mostly used linear search whenever the list is unsorted.<\/p>\n

How Linear Search Works?<\/h3>\n

Consider an array containing 10 elements as shown:<\/p>\n

\"Working<\/a><\/p>\n

Suppose that the element we wish to search is \u2018x\u2019. There will be two possible cases: we will either find \u2018x\u2019 in the list or not find \u2018x\u2019 in the list. If x is present in the list, the algorithm will return the index of that location, otherwise, it will return some invalid address.<\/p>\n

Let us see both of these cases:<\/p>\n

1. In case of success:<\/strong><\/p>\n

Suppose the value of \u2018x\u2019 is 12. We know that 12 is present in the array. The algorithm will start searching for 12 linearly starting from the beginning. It will first check the 0th index, compare the element at the 0th index with 12, if 12 is present there, it will return 0, else move to the next location.<\/p>\n

Here, 12 is not present at the 0th index. Therefore, the algorithm moves to the 1st index, following the same procedure. Then it moves to the next position. This traversal will continue in the same manner until we reach the 5th index and finally, the algorithm will return 5.<\/p>\n

2. In case of failure:<\/strong><\/p>\n

Suppose that the value of \u2018x\u2019 is 50. 50 is not present anywhere in the list. In this case, the algorithm will linearly traverse the whole array and in the end, it will return NULL.<\/p>\n

Example:<\/strong>
\nLet the input array be: {\u2018T\u2019, \u2018E\u2019, \u2018C\u2019, \u2018H\u2019, \u2018V\u2019, \u2018I\u2019, \u2018D\u2019, \u2018V\u2019, \u2018A\u2019, \u2018N\u2019}. Suppose we wish to search \u2018D\u2019 from the array. We will start traversing from the beginning as shown:<\/p>\n

\"Traversing<\/a><\/p>\n

Output: 6 (the index of the element).<\/p>\n

Algorithm for Linear Search<\/h3>\n

Step1:<\/strong> Initialize i := 1;
\nStep2:<\/strong> if (i>n) exit;
\nStep3:<\/strong> Repeat step4 to step5 while i<=n;
\nStep4:<\/strong> If A[i] == x, print i;
\nStep5:<\/strong> Set i := i+1;
\nStep6:<\/strong> Else print element not found;
\nStep7<\/strong>: Exit;<\/p>\n

Pseudo-code of Linear Search<\/h3>\n
int Linear_Search(list, key)\n{\n    for(i=0; i<n; i++)\n    {\n        if(A[i] == key)\n            return i;\n    }\n}\n<\/pre>\n
Complexity of Linear Search<\/h3>\n
The space complexity for the linear search algorithm in every case is O(1). Time complexity is different in different cases and varies according to the input.<\/p>\n
The following table gives the time complexity of the linear search algorithm:<\/p>\n\n\n\n\n\n\n
Case<\/b><\/td>\nTime complexity<\/b><\/td>\n<\/tr>\n
Best case<\/span><\/td>\nO(1)<\/span><\/td>\n<\/tr>\n
Average case<\/span><\/td>\nO(n)<\/span><\/td>\n<\/tr>\n
Worst case<\/span><\/td>\nO(n)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Linear search implementation in C:<\/h4>\n
int Linear_search(int arr[], int n, int key)\n{\n    int i;\n    for (i = 0; i<n; i++)\n        if (arr[i] == key)  \/\/key is the lement to be searched\n            return i;\n    return -1;  \/\/when the element is not present inside the array\n}\n \n \nint main(void)\n{\n    int arr[] = { 5, 3, 6, 2, 20, 7};\n    int key = 20;\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n   \n    \n    int result = Linear_search(arr, n, key);\n    if(result == -1)\n        printf(\"Element is not present in array\")\n    Else\n        printf(\"Element is present at index %d\", result);\n    return 0;\n}\n<\/pre>\n
Implementation of Linear Search In C++<\/h4>\n
#include <iostream>\nusing namespace std;\n \nint Linear_search(int arr[], int n, int key)\n{\n    int i;\n    for (i = 0; i < n; i++)\n        if (arr[i] == key)\n            return i;\n    return -1;\n}\n \nint main(void)\n{\n    int arr[] = {10, 15, 2, 43, 21, 15};\n    int key = 10;\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n   \n    int  result = Linear_search(arr, n, key);\n    if (result == -1)\n        cout << \"Element is not present in array\"\n    else\n        cout << \"Element found at location \" << result+1;\n    return 0;\n}\n<\/pre>\n
Linear Search Implementation in Java<\/h4>\n
class TechVidvan\n{\n    public static int Linear_search(int arr[], int key)\n    {\n        int n = arr.length;\n        for (int i = 0; i < n; i++)\n        {\n            if (arr[i] == key)\n                return i;\n        }\n        return -1;\n    }\n \n   \npublic static void main(String args[])\n    {\n        int arr[] = { 12, 15, 20, 3, 5};\n        int key = 10;\n \n        \n        int result = Linear_search(arr, key);\n        if (result == -1)\n            System.out.print(\n                \"Element is not present in array\");\n        else\n            System.out.print(\"Element is present at index \"\n                             + result);\n    }\n<\/pre>\n
Implementation of Linear Search in Python:<\/h4>\n
def Linear_search(arr, n, key):\n \n    for i in range(0, n):\n        if (arr[i] == key):\n            return i\n    return -1\n \narr = [12, 3, 24, 10, 4]\nkey = 10\nn = len(arr)\n \nresult = Linear_search(arr, n, key)\nif(result == -1):\n    print(\"Element is not present in array\")\nelse:\n    print(\"Element is present at index\", result)\n<\/pre>\n
Conclusion<\/h3>\n
Whenever we have lots of data in a list and we need to search for one particular item, we need a searching method. Linear search is used whenever the list is unsorted.<\/p>\n
This article studied the linear search algorithm and how it is implemented to search for items in a given list.<\/p>\n","protected":false},"excerpt":{"rendered":"
Searching is a technique used to find out a particular element from a given list of elements. We can perform searching on any data structure such as arrays, linked lists, trees, graphs, etc. If...<\/p>\n","protected":false},"author":1,"featured_media":81461,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[3644,3645],"class_list":["post-81396","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-linear-search","tag-linear-search-in-data-structure"],"yoast_head":"\nLinear Search in Data Structure - TechVidvan<\/title>\n<meta name=\"description\" content=\"Learn about the linear search in data structure, its working, algorithm and how it is implemented in different languages.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Linear Search in Data Structure - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Learn about the linear search in data structure, its working, algorithm and how it is implemented in different languages.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-06-29T03:30:56+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Linear-Search-in-DS.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Linear Search in Data Structure - TechVidvan","description":"Learn about the linear search in data structure, its working, algorithm and how it is implemented in different languages.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/","og_locale":"en_US","og_type":"article","og_title":"Linear Search in Data Structure - TechVidvan","og_description":"Learn about the linear search in data structure, its working, algorithm and how it is implemented in different languages.","og_url":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-06-29T03:30:56+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Linear-Search-in-DS.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Linear Search in Data Structure","datePublished":"2021-06-29T03:30:56+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/"},"wordCount":588,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Linear-Search-in-DS.jpg","keywords":["Linear Search","Linear Search in data structure"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/","url":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/","name":"Linear Search in Data Structure - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Linear-Search-in-DS.jpg","datePublished":"2021-06-29T03:30:56+00:00","description":"Learn about the linear search in data structure, its working, algorithm and how it is implemented in different languages.","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Linear-Search-in-DS.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/TV-Linear-Search-in-DS.jpg","width":1200,"height":628,"caption":"Linear Search in Data Structure"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/linear-search-in-data-structure\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Linear Search in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/81396","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=81396"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/81396\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/81461"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=81396"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=81396"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=81396"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}