{"id":9925,"date":"2021-07-09T11:03:01","date_gmt":"2021-07-09T05:33:01","guid":{"rendered":"https:\/\/python-programs.com\/?p=9925"},"modified":"2021-11-22T18:50:10","modified_gmt":"2021-11-22T13:20:10","slug":"search-implementations-linear-and-binary","status":"publish","type":"post","link":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/","title":{"rendered":"Search implementations: Linear and Binary"},"content":{"rendered":"

Prerequisites<\/strong><\/p>\n

To learn about Linear and Binary search, you’ll need to have a good understanding of:<\/p>\n

    \n
  1. Python 3<\/li>\n
  2. Basic Python data structure concepts – lists<\/li>\n<\/ol>\n

    Introduction<\/strong><\/p>\n

    Often we will have to find an element from a given data structure like lists, linked lists or binary trees. An efficient searching technique saves a great amount of time and improves performance. In this tutorial, we are going to see two very commonly used searching algorithms.<\/p>\n

    Linear Search<\/h2>\n

    So if you were to search \u201cHarry Potter\u201d, from a shelf in a poorly lit room how would you go about it? You would start at one end, take one book at a time and check if it’s Harry Potter or not. You will use a brute force methodology which checks every book until the Harry Potter is found or the end of the shelf is reached. Best case scenario would be when Harry Potter is the first book and worst case would be the book not in there at all. Either way, you can know this only by checking each and every book. This is exactly what Linear Search is.<\/p>\n

    Binary Search<\/h2>\n

    What if you were to search for Harry Potter from a shelf of books which are ordered alphabetically? Would you start searching from the start? Definitely not! You would start somewhere near the middle and check the first letter of the books and then go back or forward from there to find the ‘H’ titles. This means that you won\u2019t be looking at all the books, thus saving time. You also won’t need to go through the entire shelf to know whether the book is there or not. At a given point you are eliminating many books which you will never look at. Binary Search is similar to this.<\/p>\n

    NOTE:<\/b>\u00a0Linear Search can be done on both sorted and unsorted items but Binary Search can\u00a0only<\/em>\u00a0be done on a sorted set of items.<\/p>\n

    Implementation<\/h3>\n

    Now that you know what Linear and Binary Search methodologies are, let us look at how these searches would work on a list of numbers.<\/p>\n

    Linear Search<\/h4>\n

    Given list A = [6,3,9,0,5,8,2] find if 0 is present in this list or not.<\/p>\n

    Algorithm<\/h4>\n
      \n
    1. Take one number at a time from list A<\/li>\n
    2. Compare it with 0 and check if it is a match:\n
        \n
      1. If yes, return True<\/li>\n
      2. If not, return False<\/li>\n<\/ol>\n<\/li>\n
      3. If the end of the list is met, return False<\/li>\n<\/ol>\n

        Code<\/p>\n

        def linearSearch(ls,data):\r\n\r\n   for item in ls:\r\n       if item == data:\r\n           return True\r\n   return False<\/pre>\n
        print(linearSearch([6,3,9,5,8,2],0))<\/p>\n
        Binary Search<\/h4>\n
        The idea is to keep comparing the element with the middle value. This way with each search we eliminate one half of the list.<\/p>\n
        Algorithm<\/h4>\n
          \n
        1. Keep track of two pointers First and Last, these are incremented or decremented to limit the part of the list to be searched.<\/li>\n
        2. Find the middle element of the list: mid = ( length of the list )\/2<\/li>\n
        3. Compare the middle element with the value to be found<\/li>\n
        4. Check if the middle element is lesser than the value to be found:\n
            \n
          1. If yes, the element must lie on the second half of the list<\/li>\n
          2. If no, the element must lie on the first half of the list<\/li>\n<\/ol>\n<\/li>\n
          3. Repeat steps 1 through 3 until the element is found or the end of the list is reached<\/li>\n<\/ol>\n
            NOTE:<\/b>\u00a0The list continues to get divided into two and the middle element gets compared until the element is found or no more elements are left to compare with.<\/p>\n
            Code<\/p>\n
            Given list B = [2,5,7,8,9,11,14,16] find if 14 is present in this list or not.<\/p>\n
            def binarySearch(ls,data):\r\n   first = 0\r\n   last = len(ls)-1\r\n   done = False   \r\n\r\n    while first<=last and not done:\r\n       mid = (first+last)\/\/2\r\n          if ls[mid] == data:\r\n           done = True\r\n       else:\r\n           if ls[mid] > data:\r\n               last = last-1\r\n           else:\r\n               first = first+1\r\n   return done \r\n\r\nprint(binarySearch([2,5,7,8,9,11,14,16],4))<\/pre>\n\n\n\n\n\n\n
            Round<\/td>\nFirst<\/td>\nLast<\/td>\nMid<\/td>\nls[mid]<\/td>\nResult<\/td>\n<\/tr>\n
            1<\/td>\n0<\/td>\n7<\/td>\n3<\/td>\n8<\/td>\n8<14<\/td>\n<\/tr>\n
            2<\/td>\n4<\/td>\n7<\/td>\n5<\/td>\n11<\/td>\n11<14<\/td>\n<\/tr>\n
            3<\/td>\n6<\/td>\n7<\/td>\n6<\/td>\n14<\/td>\n14=14<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
            NOTE:<\/b>\u00a0To find the mid element, \u201c(first+last)\/\/2\u201d is used instead of \u201c(first+last)\/2\u201d. This gives us whole numbers especially when the length of the list is odd. Try 9\/2 and 9\/\/2 in your Python IDLE to get a better understanding.<\/p>\n
            Try out\u00a0this\u00a0animation for a better understanding of both these search algorithms. Try to find the first element of the array. Which is faster?<\/p>\n
            Conclusion<\/strong><\/p>\n
            From the above explanation, it must be clear that Binary Search is consistently faster than Linear Search. If you are familiar with o(n) notation, Linear Search is o(n) and Binary Search is log(n)<\/p>\n
            You can perform Linear Searches on a sorted list as well with a small optimization. You can stop the search once the number to be found exceeds the element being compared to. For instance, you want to search for 12 from the list [2,4,5,13,16,19], once you reach 13 you can stop because there is no way that 12 is going to come after 13 in a sorted list.<\/p>\n
            In this tutorial, we have discussed only the iterative method of Binary Search. Try to implement the recursive approach on your own. \u00a0Also, learn about the uses of these searches and when to apply them. That\u2019s all for this tutorial. Happy Pythoning!<\/p>\n","protected":false},"excerpt":{"rendered":"
            Prerequisites To learn about Linear and Binary search, you’ll need to have a good understanding of: Python 3 Basic Python data structure concepts – lists Introduction Often we will have to find an element from a given data structure like lists, linked lists or binary trees. An efficient searching technique saves a great amount of …<\/p>\n
              Search implementations: Linear and Binary<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true},"categories":[5],"tags":[],"yoast_head":"\nSearch implementations: Linear and Binary - Python Programs<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Search implementations: Linear and Binary - Python Programs\" \/>\n<meta property=\"og:description\" content=\"Prerequisites To learn about Linear and Binary search, you’ll need to have a good understanding of: Python 3 Basic Python data structure concepts – lists Introduction Often we will have to find an element from a given data structure like lists, linked lists or binary trees. An efficient searching technique saves a great amount of … Search implementations: Linear and Binary Read More »\" \/>\n<meta property=\"og:url\" content=\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/\" \/>\n<meta property=\"og:site_name\" content=\"Python Programs\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/btechgeeks\" \/>\n<meta property=\"article:published_time\" content=\"2021-07-09T05:33:01+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-11-22T13:20:10+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@btech_geeks\" \/>\n<meta name=\"twitter:site\" content=\"@btech_geeks\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"veer\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Organization\",\"@id\":\"https:\/\/python-programs.com\/#organization\",\"name\":\"BTech Geeks\",\"url\":\"https:\/\/python-programs.com\/\",\"sameAs\":[\"https:\/\/www.instagram.com\/btechgeeks\/\",\"https:\/\/www.linkedin.com\/in\/btechgeeks\",\"https:\/\/in.pinterest.com\/btechgeek\/\",\"https:\/\/www.youtube.com\/channel\/UC9MlCqdJ3lKqz2p5114SDIg\",\"https:\/\/www.facebook.com\/btechgeeks\",\"https:\/\/twitter.com\/btech_geeks\"],\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/python-programs.com\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/python-programs.com\/wp-content\/uploads\/2020\/11\/BTechGeeks.png\",\"contentUrl\":\"https:\/\/python-programs.com\/wp-content\/uploads\/2020\/11\/BTechGeeks.png\",\"width\":350,\"height\":70,\"caption\":\"BTech Geeks\"},\"image\":{\"@id\":\"https:\/\/python-programs.com\/#\/schema\/logo\/image\/\"}},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/python-programs.com\/#website\",\"url\":\"https:\/\/python-programs.com\/\",\"name\":\"Python Programs\",\"description\":\"Python Programs with Examples, How To Guides on Python\",\"publisher\":{\"@id\":\"https:\/\/python-programs.com\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/python-programs.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#webpage\",\"url\":\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/\",\"name\":\"Search implementations: Linear and Binary - Python Programs\",\"isPartOf\":{\"@id\":\"https:\/\/python-programs.com\/#website\"},\"datePublished\":\"2021-07-09T05:33:01+00:00\",\"dateModified\":\"2021-11-22T13:20:10+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/python-programs.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Search implementations: Linear and Binary\"}]},{\"@type\":\"Article\",\"@id\":\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#webpage\"},\"author\":{\"@id\":\"https:\/\/python-programs.com\/#\/schema\/person\/9f9e30fd3f415217a11ac0d939213b7f\"},\"headline\":\"Search implementations: Linear and Binary\",\"datePublished\":\"2021-07-09T05:33:01+00:00\",\"dateModified\":\"2021-11-22T13:20:10+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#webpage\"},\"wordCount\":793,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/python-programs.com\/#organization\"},\"articleSection\":[\"Python\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#respond\"]}]},{\"@type\":\"Person\",\"@id\":\"https:\/\/python-programs.com\/#\/schema\/person\/9f9e30fd3f415217a11ac0d939213b7f\",\"name\":\"veer\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/python-programs.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/f1f6915d5328abaea9a64249313d1c55?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/f1f6915d5328abaea9a64249313d1c55?s=96&d=mm&r=g\",\"caption\":\"veer\"},\"sameAs\":[\"https:\/\/python-programs.com\"],\"url\":\"https:\/\/python-programs.com\/author\/veer\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Search implementations: Linear and Binary - Python Programs","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:\/\/python-programs.com\/search-implementations-linear-and-binary\/","og_locale":"en_US","og_type":"article","og_title":"Search implementations: Linear and Binary - Python Programs","og_description":"Prerequisites To learn about Linear and Binary search, you’ll need to have a good understanding of: Python 3 Basic Python data structure concepts – lists Introduction Often we will have to find an element from a given data structure like lists, linked lists or binary trees. An efficient searching technique saves a great amount of … Search implementations: Linear and Binary Read More »","og_url":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/","og_site_name":"Python Programs","article_publisher":"https:\/\/www.facebook.com\/btechgeeks","article_published_time":"2021-07-09T05:33:01+00:00","article_modified_time":"2021-11-22T13:20:10+00:00","twitter_card":"summary_large_image","twitter_creator":"@btech_geeks","twitter_site":"@btech_geeks","twitter_misc":{"Written by":"veer","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Organization","@id":"https:\/\/python-programs.com\/#organization","name":"BTech Geeks","url":"https:\/\/python-programs.com\/","sameAs":["https:\/\/www.instagram.com\/btechgeeks\/","https:\/\/www.linkedin.com\/in\/btechgeeks","https:\/\/in.pinterest.com\/btechgeek\/","https:\/\/www.youtube.com\/channel\/UC9MlCqdJ3lKqz2p5114SDIg","https:\/\/www.facebook.com\/btechgeeks","https:\/\/twitter.com\/btech_geeks"],"logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/python-programs.com\/#\/schema\/logo\/image\/","url":"https:\/\/python-programs.com\/wp-content\/uploads\/2020\/11\/BTechGeeks.png","contentUrl":"https:\/\/python-programs.com\/wp-content\/uploads\/2020\/11\/BTechGeeks.png","width":350,"height":70,"caption":"BTech Geeks"},"image":{"@id":"https:\/\/python-programs.com\/#\/schema\/logo\/image\/"}},{"@type":"WebSite","@id":"https:\/\/python-programs.com\/#website","url":"https:\/\/python-programs.com\/","name":"Python Programs","description":"Python Programs with Examples, How To Guides on Python","publisher":{"@id":"https:\/\/python-programs.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/python-programs.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#webpage","url":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/","name":"Search implementations: Linear and Binary - Python Programs","isPartOf":{"@id":"https:\/\/python-programs.com\/#website"},"datePublished":"2021-07-09T05:33:01+00:00","dateModified":"2021-11-22T13:20:10+00:00","breadcrumb":{"@id":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/python-programs.com\/search-implementations-linear-and-binary\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/python-programs.com\/"},{"@type":"ListItem","position":2,"name":"Search implementations: Linear and Binary"}]},{"@type":"Article","@id":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#article","isPartOf":{"@id":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#webpage"},"author":{"@id":"https:\/\/python-programs.com\/#\/schema\/person\/9f9e30fd3f415217a11ac0d939213b7f"},"headline":"Search implementations: Linear and Binary","datePublished":"2021-07-09T05:33:01+00:00","dateModified":"2021-11-22T13:20:10+00:00","mainEntityOfPage":{"@id":"https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#webpage"},"wordCount":793,"commentCount":0,"publisher":{"@id":"https:\/\/python-programs.com\/#organization"},"articleSection":["Python"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/python-programs.com\/search-implementations-linear-and-binary\/#respond"]}]},{"@type":"Person","@id":"https:\/\/python-programs.com\/#\/schema\/person\/9f9e30fd3f415217a11ac0d939213b7f","name":"veer","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/python-programs.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/f1f6915d5328abaea9a64249313d1c55?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/f1f6915d5328abaea9a64249313d1c55?s=96&d=mm&r=g","caption":"veer"},"sameAs":["https:\/\/python-programs.com"],"url":"https:\/\/python-programs.com\/author\/veer\/"}]}},"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/posts\/9925"}],"collection":[{"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/comments?post=9925"}],"version-history":[{"count":3,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/posts\/9925\/revisions"}],"predecessor-version":[{"id":12177,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/posts\/9925\/revisions\/12177"}],"wp:attachment":[{"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/media?parent=9925"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/categories?post=9925"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/python-programs.com\/wp-json\/wp\/v2\/tags?post=9925"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}