{"id":24942,"date":"2017-10-15T13:50:11","date_gmt":"2017-10-15T08:20:11","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=24942"},"modified":"2017-10-15T13:50:11","modified_gmt":"2017-10-15T08:20:11","slug":"linear-search","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/linear-search\/","title":{"rendered":"Linear Search"},"content":{"rendered":"<p><strong>Problem:<\/strong> Given an array arr[] of n elements, write a function to search a given element x in arr[].<\/p>\n<p>A simple approach is to do linear search, i.e<\/p>\n<ul>\n<li>Start from the leftmost element of arr[] and one by one compare x with each element of arr[]<\/li>\n<li>If x matches with an element, return the index.<\/li>\n<li>If x doesn\u2019t match with any of elements, return -1.<\/li>\n<\/ul>\n<p><strong>Example:<\/strong><\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-24945\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/linear-search.png\" alt=\"Linear Search\" width=\"593\" height=\"452\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/linear-search.png 593w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/linear-search-300x229.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/linear-search-74x55.png 74w\" sizes=\"(max-width: 593px) 100vw, 593px\" \/><\/p>\n<p>C and C++<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Linearly%20search%20x%20in%20arr%5B%5D.%20%20If%20x%20is%20present%20then%20return%20its%20%0A%2F%2F%20location%2C%20%20otherwise%20return%20-1%0Aint%20search(int%20arr%5B%5D%2C%20int%20n%2C%20int%20x)%0A%7B%0A%20%20%20%20int%20i%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20return%20i%3B%0A%20%20%20%20return%20-1%3B%0A%7D\u201d message=\u201dC and C++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p>Python<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Searching%20an%20element%20in%20a%20list%2Farray%20in%20python%0A%23%20can%20be%20simply%20done%20using%20\u2019in\u2019%20operator%0A%23%20Example%3A%0A%23%20if%20x%20in%20arr%3A%0A%23%20%20%20print%20arr.index(x)%0A%20%0A%23%20If%20you%20want%20to%20implement%20Linear%20Search%20in%20python%0A%20%0A%23%20Linearly%20search%20x%20in%20arr%5B%5D%0A%23%20If%20x%20is%20present%20then%20return%20its%20location%0A%23%20else%20return%20-1%0A%20%0Adef%20search(arr%2C%20x)%3A%0A%20%0A%20%20%20%20for%20i%20in%20range(len(arr))%3A%0A%20%0A%20%20%20%20%20%20%20%20if%20arr%5Bi%5D%20%3D%3D%20x%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20i%0A%20%0A%20%20%20%20return%20-1\u2033 message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Java<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dclass%20LinearSearch%0A%7B%0A%20%20%20%20%2F%2F%20This%20function%20returns%20index%20of%20element%20x%20in%20arr%5B%5D%0A%20%20%20%20static%20int%20search(int%20arr%5B%5D%2C%20int%20n%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Return%20the%20index%20of%20the%20element%20if%20the%20element%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20is%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20i%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20return%20-1%20if%20the%20element%20is%20not%20found%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20%7D%0A%7D%20\u2033 message=\u201dJava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>The time complexity of above algorithm is O(n).<\/p>\n<p>Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster searching comparison to Linear search.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Linear Search &#8211; searching and sorting &#8211; algorithm -A simple approach is to do linear search, Start from the leftmost element of arr[] and one by one compare<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[82509,1],"tags":[70054,70058,70065,70050,70078,70096,70052,70109,70076,70107,70120,70081,70090,70082,70113,70088,70086,70115,70111,70098,70116,70077,70047,70064,70067,70048,70110,70103,70093,70112,70119,70069,70068,70085,70079,70035,70059,70063,70083,70066,70061,70117,70074,70080,70060,70070,70071,70095,70075,70049,70084,1422,70073,70051,70046,70056,70118,70089,70099,70114,70097,70106,70072,70094,70104,70105,70057,70062,70053,70055,70087,70091,70108,70100,70102,70092,70101],"class_list":["post-24942","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree-2","category-coding","tag-algorithm","tag-algorithm-for-linear-search","tag-algorithm-of-linear-search","tag-array","tag-array-search","tag-arrays-binarysearch","tag-binary-search","tag-binary-search-algorithm-in-data-structure","tag-binary-search-c","tag-binary-search-c-program","tag-binary-search-code","tag-binary-search-complexity","tag-binary-search-definition","tag-binary-search-example","tag-binary-search-in-c-program","tag-binary-search-in-data-structure","tag-binary-search-program","tag-binary-search-program-in-data-structure","tag-binary-search-topcoder","tag-binary-search-using-recursion","tag-c-program-for-binary-search","tag-c-program-for-linear-search","tag-c-programming","tag-complexity-of-linear-search","tag-complexity-of-linear-search-algorithm","tag-data-structures","tag-difference-between-binary-search-and-linear-search","tag-difference-between-linear-and-binary-search","tag-difference-between-linear-search-and-binary-search","tag-geeksforgeeks-c-programming","tag-indexed-sequential-search","tag-linear-and-binary-search","tag-linear-array-in-data-structure","tag-linear-hashing","tag-linear-probing","tag-linear-search-algorithm-in-c","tag-linear-search-algorithm-in-data-structure","tag-linear-search-and-binary-search","tag-linear-search-c-program","tag-linear-search-complexity","tag-linear-search-example","tag-linear-search-in-c-program","tag-linear-search-in-data-structure","tag-linear-search-in-java","tag-linear-search-java","tag-linear-search-program","tag-linear-search-program-in-data-structure","tag-linear-search-program-in-java","tag-linear-sort","tag-linked-list","tag-list-of-search-algorithms","tag-pointer","tag-program-for-linear-search","tag-queue","tag-quicksort","tag-recursion","tag-search-an-element-in-an-array","tag-search-in-array","tag-search-inc","tag-search-techniques","tag-searching-algorithms-in-c","tag-searching-algorithms-in-data-structure","tag-searching-in-data-structure","tag-searching-program-in-c","tag-searching-techniques-in-c","tag-searching-techniques-in-data-structure","tag-sequential-search","tag-sequential-search-algorithm","tag-source-code","tag-stack","tag-the-complexity-of-linear-search-algorithm-is","tag-time-complexity-of-linear-search","tag-types-of-searching-algorithms","tag-types-of-searching-in-data-structure","tag-what-is-linear-data-structure","tag-what-is-linear-search","tag-what-is-searching-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24942","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=24942"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24942\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=24942"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=24942"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=24942"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}