{"id":27844,"date":"2022-12-27T01:50:59","date_gmt":"2022-12-26T20:20:59","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/"},"modified":"2022-12-27T01:50:59","modified_gmt":"2022-12-26T20:20:59","slug":"solved-recursive-binary-search-algorithm-python-closed","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/","title":{"rendered":"[Solved] Recursive Binary search algorithm &#8211; Python [closed]"},"content":{"rendered":"<p> [ad_1]<br \/>\n<\/p>\n<div id=\"answer-21145864\" class=\"answer js-answer accepted-answer js-accepted-answer\" data-answerid=\"21145864\" data-parentid=\"21145552\" data-score=\"0\" data-position-on-page=\"1\" data-highest-scored=\"1\" data-question-has-accepted-highest-score=\"1\" itemprop=\"acceptedAnswer\" itemscope itemtype=\"https:\/\/schema.org\/Answer\">\n<div class=\"post-layout\">\n<div class=\"votecell post-layout--left\"><\/div>\n<div class=\"answercell post-layout--right\">\n<div class=\"s-prose js-post-body\" itemprop=\"text\">\n<p>Your existing function has at least two major problems: It doesn&#8217;t <code>return<\/code> the value from the recursive calls, meaning that it usually ends up returning <code>None<\/code> if it finishes; it uses the wrong bounds to slice the list, meaning half the time it ends up with infinite recursion.<\/p>\n<p>If you fix those, then all you have to do is return the index instead of True, and something else (e.g., -1, or raise an exception) instead of False. That means the recursive calls will get the index into the slice instead of the whole list, but they know the offset and can adjust it.<\/p>\n<p>So, first:<\/p>\n<pre><code>if len(L) == 1:\n    if L[0] == val:\n        # return True\n        return 0\n    else:\n        # return False\n        raise ValueError('not found')\nelse:\n    hi = len(L)\n    lo = 0\n    mid = (hi + lo)\/\/2\n    if val == L[mid]:\n        # return True\n        return mid\n    elif val &gt; L[mid]:\n        # return bin_search(val,L[mid + 1:])\n        return mid + 1 + bin_search(val,L[mid + 1:])\n    elif val &lt; L[mid]:\n        # no change here, because the offset is 0\n        return bin_search(val,L[:mid])\n<\/code><\/pre>\n<p>And that&#8217;s it. It should be obvious that this is doing the exact same sequence of recursive calls, and the only extra work is adding <code>mid + 1<\/code> in just under half the cases, so it still has the same complexity.<\/p>\n<\/p><\/div>\n<div class=\"mt24\"><\/div>\n<\/div>\n<p>            <span class=\"d-none\" itemprop=\"commentCount\"><\/span> <\/p><\/div>\n<\/div>\n<p>[ad_2]<\/p>\n<p>solved Recursive Binary search algorithm &#8211; Python [closed] <\/p>\n","protected":false},"excerpt":{"rendered":"<p>[ad_1] Your existing function has at least two major problems: It doesn&#8217;t return the value from the recursive calls, meaning that it usually ends up returning None if it finishes; it uses the wrong bounds to slice the list, meaning half the time it ends up with infinite recursion. If you fix those, then all &#8230; <a title=\"[Solved] Recursive Binary search algorithm &#8211; Python [closed]\" class=\"read-more\" href=\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/\" aria-label=\"More on [Solved] Recursive Binary search algorithm &#8211; Python [closed]\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[349],"class_list":["post-27844","post","type-post","status-publish","format-standard","hentry","category-solved","tag-python"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.5 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>[Solved] Recursive Binary search algorithm - Python [closed] - JassWeb<\/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:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Recursive Binary search algorithm - Python [closed] - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] Your existing function has at least two major problems: It doesn&#8217;t return the value from the recursive calls, meaning that it usually ends up returning None if it finishes; it uses the wrong bounds to slice the list, meaning half the time it ends up with infinite recursion. If you fix those, then all ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-12-26T20:20:59+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Recursive Binary search algorithm &#8211; Python [closed]\",\"datePublished\":\"2022-12-26T20:20:59+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/\"},\"wordCount\":162,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"python\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/\",\"name\":\"[Solved] Recursive Binary search algorithm - Python [closed] - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-12-26T20:20:59+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Recursive Binary search algorithm &#8211; Python [closed]\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Recursive Binary search algorithm - Python [closed] - JassWeb","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:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Recursive Binary search algorithm - Python [closed] - JassWeb","og_description":"[ad_1] Your existing function has at least two major problems: It doesn&#8217;t return the value from the recursive calls, meaning that it usually ends up returning None if it finishes; it uses the wrong bounds to slice the list, meaning half the time it ends up with infinite recursion. If you fix those, then all ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/","og_site_name":"JassWeb","article_published_time":"2022-12-26T20:20:59+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Recursive Binary search algorithm &#8211; Python [closed]","datePublished":"2022-12-26T20:20:59+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/"},"wordCount":162,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["python"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/","url":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/","name":"[Solved] Recursive Binary search algorithm - Python [closed] - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-12-26T20:20:59+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-recursive-binary-search-algorithm-python-closed\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Recursive Binary search algorithm &#8211; Python [closed]"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/27844","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=27844"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/27844\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=27844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=27844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=27844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}