{"id":96365,"date":"2021-06-10T09:00:49","date_gmt":"2021-06-10T03:30:49","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=96365"},"modified":"2021-06-03T20:43:19","modified_gmt":"2021-06-03T15:13:19","slug":"linear-search-in-data-structure","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/","title":{"rendered":"Linear Search in Data Structure"},"content":{"rendered":"

Let us consider a scenario where you have to find a book in your personal stack of books. Assuming that the stack is not arranged in any order, the only way to find a book is to read the title of each book. And when you find the desired book you stop this process and don\u2019t look into further books. This is a real-life example of linear search.<\/p>\n

Linear Search<\/h3>\n

Linear search is the most basic search algorithm in the data structure. It is used to search any element in a linear data structure like arrays and linked lists. Linear Search algorithm compares the search element to each element of the Data Structure and returns the location of the element if found.<\/p>\n

Method to use Linear Search<\/h4>\n

1. Start from the first element and compare each element with the search element.
\n2. If the element is found, return at which position element was found.
\n3. If the element is not found, return -1.<\/p>\n

Algorithm for Linear Search<\/h4>\n

Steps for Linear search are as follows:<\/p>\n

Linear_Search ( Array A [ n ], search_element x)<\/span><\/p>\n

1: Set i to 1<\/span><\/p>\n

2: if i > n then go to step 7<\/span><\/p>\n

3: if A[i] = x then go to step 6<\/span><\/p>\n

4: assign i+1 to i<\/span><\/p>\n

5: Go to Step 2<\/span><\/p>\n

6: Print Element x Found at index i and exit<\/span><\/p>\n

7: display \u201celement not found\u201d<\/span><\/p>\n

Pseudocode for Linear Search<\/h4>\n
procedure linear_search (array, value)\r\n\r\n   for each item in the array\r\n      if item == value\r\n         return the item's index\r\n      end if\r\n   end for\r\n\r\nend procedure\r\n\r\n<\/pre>\n
Example of Linear Search<\/strong><\/p>\n
Input Array:<\/b> {\u2018D\u2019,\u2019A\u2019,\u2019T\u2019,\u2019A\u2019,\u2019F\u2019,\u2019L\u2019,\u2019A\u2019,\u2019I\u2019,\u2019R\u2019}<\/span><\/p>\n
Search Element:<\/b> \u2018I\u201d<\/span><\/p>\n
\"linear<\/a><\/p>\n
Output:<\/b><\/p>\n
\u2018I\u2019 is present at index 7<\/span><\/div>\n
Linear Search Implementation in C++<\/h3>\n
#include <iostream>\r\nusing namespace std;\r\n \r\nint search(int arr[], int n, int x)\r\n{\r\n    int i;\r\n    for (i = 0; i < n; i++)\r\n        if (arr[i] == x)\r\n            return i;\r\n    return -1;\r\n}\r\n \r\nint main(void)\r\n{\r\n    int arr[] = { 2, 3, 4, 10, 40 };\r\n    int x = 10;\r\n    int n = sizeof(arr) \/ sizeof(arr[0]);\r\n   \r\n    int  result = search(arr, n, x);\r\n    if (result == -1)\r\n        cout << \"Element is not present in array\"\r\n    else\r\n        cout << \"Element found at location \" << result+1;\r\n    return 0;\r\n}\r\n<\/pre>\n
Implementation of Linear Search in C<\/h3>\n
#include <stdio.h>\r\n \r\nint search(int arr[], int n, int x)\r\n{\r\n    int i;\r\n    for (i = 0; i < n; i++)\r\n        if (arr[i] == x)\r\n            return i;\r\n    return -1;\r\n}\r\n \r\n \r\nint main(void)\r\n{\r\n    int arr[] = { 2, 3, 4, 10, 40 };\r\n    int x = 10;\r\n    int n = sizeof(arr) \/ sizeof(arr[0]);\r\n   \r\n    \r\n    int result = search(arr, n, x);\r\n    if(result == -1)\r\n        printf(\"Element is not present in array\")\r\n    Else\r\n        printf(\"Element is present at index %d\", result);\r\n    return 0;\r\n}\r\n<\/pre>\n
Linear Search Implementation in Java<\/h3>\n
class DataFlair\r\n{\r\n    public static int search(int arr[], int x)\r\n    {\r\n        int n = arr.length;\r\n        for (int i = 0; i < n; i++)\r\n        {\r\n            if (arr[i] == x)\r\n                return i;\r\n        }\r\n        return -1;\r\n    }\r\n \r\n   \r\npublic static void main(String args[])\r\n    {\r\n        int arr[] = { 2, 3, 4, 10, 40 };\r\n        int x = 10;\r\n \r\n        \r\n        int result = search(arr, x);\r\n        if (result == -1)\r\n            System.out.print(\r\n                \"Element is not present in array\");\r\n        else\r\n            System.out.print(\"Element is present at index \"\r\n                             + result);\r\n    }\r\n<\/pre>\n
Implementation of Linear Search in Python<\/h3>\n
def search(arr, n, x):\r\n \r\n    for i in range(0, n):\r\n        if (arr[i] == x):\r\n            return i\r\n    return -1\r\n \r\narr = [2, 3, 4, 10, 40]\r\nx = 10\r\nn = len(arr)\r\n \r\nresult = search(arr, n, x)\r\nif(result == -1):\r\n    print(\"Element is not present in array\")\r\nelse:\r\n    print(\"Element is present at index\", result)\r\n\r\n\r\n\r\n<\/pre>\n
Time Complexity of Linear Search<\/h3>\n
The worst-case time complexity of a linear search algorithm is O(n) since it compares the search element to all the elements in an array or linked list.\u00a0<\/span><\/p>\n
Due to this reason, linear search is not common since other algorithms like binary search and hash table perform search operations at a very fast rate.<\/span><\/p>\n\n\n\n\n\n
Complexity<\/b><\/td>\nBest Case<\/b><\/td>\nAverage Case<\/b><\/td>\nWorst Case<\/b><\/td>\n<\/tr>\n
Time Complexity<\/b><\/td>\nO(1)<\/span><\/td>\nO(n)<\/span><\/td>\nO(n)<\/span><\/td>\n<\/tr>\n
Space complexity<\/b><\/td>\n<\/td>\n<\/td>\nO(1)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Conclusion<\/h3>\n
In this article, we witnessed the most basic searching technique used for small inputs. Linear search is used for small inputs sizes. We have some more efficient algorithms for large inputs that we will study in future articles. <\/span><\/p>\n
The time complexity of the linear search algorithm for the worst case is very non-efficient and therefore is not used widely in the professional world.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"
Let us consider a scenario where you have to find a book in your personal stack of books. Assuming that the stack is not arranged in any order, the only way to find a...<\/p>\n","protected":false},"author":7,"featured_media":96556,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24020],"tags":[24481,24482,24480],"class_list":["post-96365","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure-tutorials","tag-linear-search","tag-linear-search-algorithm","tag-linear-search-in-data-structure"],"yoast_head":"\nLinear Search in Data Structure - DataFlair<\/title>\n<meta name=\"description\" content=\"In computer science, a linear search or sequential search is a method for finding an element within a list. Learn more about it.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/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 - DataFlair\" \/>\n<meta property=\"og:description\" content=\"In computer science, a linear search or sequential search is a method for finding an element within a list. Learn more about it.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-06-10T03:30:49+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/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=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Linear Search in Data Structure - DataFlair","description":"In computer science, a linear search or sequential search is a method for finding an element within a list. Learn more about it.","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:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/","og_locale":"en_US","og_type":"article","og_title":"Linear Search in Data Structure - DataFlair","og_description":"In computer science, a linear search or sequential search is a method for finding an element within a list. Learn more about it.","og_url":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2021-06-10T03:30:49+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Linear-Search-in-DS.jpg","type":"image\/jpeg"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/beb0cab24b7aa54423a3b50e669a9dcd"},"headline":"Linear Search in Data Structure","datePublished":"2021-06-10T03:30:49+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/"},"wordCount":414,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Linear-Search-in-DS.jpg","keywords":["Linear Search","Linear Search Algorithm","Linear Search in Data Structure"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/","url":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/","name":"Linear Search in Data Structure - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Linear-Search-in-DS.jpg","datePublished":"2021-06-10T03:30:49+00:00","description":"In computer science, a linear search or sequential search is a method for finding an element within a list. Learn more about it.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Linear-Search-in-DS.jpg","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Linear-Search-in-DS.jpg","width":1200,"height":628,"caption":"Linear Search in DS"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/linear-search-in-data-structure\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"Data Structure Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/data-structure-tutorials\/"},{"@type":"ListItem","position":3,"name":"Linear Search in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/beb0cab24b7aa54423a3b50e669a9dcd","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/c322416204232f4dd97ef3901b0a499a5d34d7ba7fe333f4bfe53a907873d293?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c322416204232f4dd97ef3901b0a499a5d34d7ba7fe333f4bfe53a907873d293?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/c322416204232f4dd97ef3901b0a499a5d34d7ba7fe333f4bfe53a907873d293?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"DataFlair Team specializes in creating clear, actionable content on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Backed by industry expertise, we make learning easy and career-oriented for beginners and pros alike.","url":"https:\/\/data-flair.training\/blogs\/author\/dfteam3\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/96365","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=96365"}],"version-history":[{"count":5,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/96365\/revisions"}],"predecessor-version":[{"id":96559,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/96365\/revisions\/96559"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/96556"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=96365"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=96365"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=96365"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}