{"id":2448,"date":"2020-11-22T04:00:10","date_gmt":"2020-11-22T04:00:10","guid":{"rendered":"https:\/\/system.camp\/?p=2448"},"modified":"2021-09-22T11:43:51","modified_gmt":"2021-09-22T11:43:51","slug":"binary-search","status":"publish","type":"post","link":"https:\/\/system.camp\/uncategorized\/binary-search\/","title":{"rendered":"Binary Search"},"content":{"rendered":"\n<p><strong>Introduction:<\/strong><\/p>\n\n\n\n<p>Binary search is one of the most important algorithms for competitive programming. You may find other uses of binary search too, these are just a few topics mentioned that use binary search heavily:<\/p>\n\n\n\n<p><em>1. Array problems<\/em><\/p>\n\n\n\n<p><em>2. Geometry problems<\/em><\/p>\n\n\n\n<p>Let me give you a real-life example, imagine you walked into a room with some numbered chairs (<strong>say 1 to 1000<\/strong>). Now you come to know that you have to sit on the chair numbered 563, of course,  you could find it by walking in a straight path and looking at each of the chair numbers. But for the sake of understanding binary search assume that<strong>&nbsp;you can jump to any chair within a fraction of time<\/strong>,<\/p>\n\n\n\n<ul><li>First, jump to the chair number numbered 500&nbsp;((1+1000)\/2). Now you see that the number 563 is greater than 500. So there is no need to search 563 at the left portion.<\/li><li>You then search between&nbsp;500 and&nbsp;1000&nbsp;and land up at 750. The search interval now reduces to&nbsp;500&nbsp;and&nbsp;750.<\/li><\/ul>\n\n\n\n<p>You follow the same process of eliminating regions until you reach a chair numbered 563. You can see that the elimination of search regions results in a very fast algorithm.<\/p>\n\n\n\n<p>You follow the same process of eliminating regions until you reach chair numbered 563. You can see that the elimination of search regions results in a very fast algorithm.<\/p>\n\n\n\n<p>This algorithm is used when the search space is&nbsp;<strong><em>monotonic<\/em><\/strong>&nbsp;in nature. What I mean to say is that you may not find&nbsp;<strong>chair 5<\/strong>&nbsp;using the same algorithm if the chairs were placed in random order.<\/p>\n\n\n\n<p>Now let\u2019s look at other applications of binary search. It can be used to find a value that satisfies an equation that is monotonic in nature. For example, take an equation, \ud835\udc65<sup>2<\/sup>\u22123 &gt; 0&nbsp;and&nbsp;\ud835\udc65 &gt; 0 should be always true. Also, you need to find the <strong>minimum<\/strong> value that would satisfy the equation. <\/p>\n\n\n\n<p>The values of <em>x<\/em> that satisfy the equation should be more than or equal to 2, i.e., the function is monotonic in nature.<\/p>\n\n\n\n<p>The answer can be found using binary search. The code-snippet using C++ is given below,<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>void solve() {\n    int low = 0 ,high = 10000, mid; \n    while(low &lt;= high) \n    { \n        mid = (low + high) \/ 2; \n        if(mid * mid - 3 > 0) { \n            high = mid - 1; \n        } else { \n            low = mid + 1; \n        } \n    } \n    cout &lt;&lt; low &lt;&lt; endl; \n} \n \nOutput : 2 <\/code><\/pre>\n\n\n\n<p><strong>You can practice some of these questions which will give you a better insight,<\/strong><\/p>\n\n\n\n<p><a href=\"http:\/\/codeforces.com\/contest\/812\/problem\/C\" class=\"rank-math-link\" target=\"_blank\" rel=\"noopener\">Sagheer and Nubian Markets<\/a><br><a href=\"http:\/\/codeforces.com\/problemset\/problem\/785\/C\" class=\"rank-math-link\" target=\"_blank\" rel=\"noopener\">Anton and Fairy Tale<\/a><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Introduction: Binary search is one of the most important algorithms for competitive programming. You may find other uses of binary search too, these are just a few topics mentioned that use binary search heavily: 1. Array problems 2. Geometry problems Let me give you a&#8230;<\/p>\n","protected":false},"author":2,"featured_media":2479,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0},"categories":[1],"tags":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/posts\/2448"}],"collection":[{"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/comments?post=2448"}],"version-history":[{"count":3,"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/posts\/2448\/revisions"}],"predecessor-version":[{"id":2480,"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/posts\/2448\/revisions\/2480"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/media\/2479"}],"wp:attachment":[{"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/media?parent=2448"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/categories?post=2448"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/system.camp\/wp-json\/wp\/v2\/tags?post=2448"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}