{"id":994,"date":"2017-03-13T06:52:19","date_gmt":"2017-03-13T13:52:19","guid":{"rendered":"http:\/\/somethingk.com\/main\/?p=994"},"modified":"2017-03-13T09:01:23","modified_gmt":"2017-03-13T16:01:23","slug":"recursive-binary-search-in-c","status":"publish","type":"post","link":"https:\/\/somethingk.com\/main\/recursive-binary-search-in-c\/","title":{"rendered":"Recursive Binary Search in C++"},"content":{"rendered":"<p>I wrote a recursive binary find that looks through a <strong>sorted<\/strong> array for a given number. \u00a0(You can use this on an unsorted array, it just isn&#8217;t as performant.)<\/p>\n<p>This is how it works, the recursive function call requires the number to search and the lowest and highest positions\u00a0in a search range. To start, you give the low position, 0, and the high position, the size of the array.\u00a0This is seen in the first function calling the recursive helper function. Each recursive call, first checks to make sure the low position is actually lower than the high, if it is not, the number was not found in the array. Next, we find the middle of the search section (right now it&#8217;s 0 to the size of the array). Let&#8217;s say our size\u00a0is 10, so we determine the middle to be 5.<\/p>\n<p>The if\/else statement then works a little magic to determine if the value we have is actually in the array. First we check if the middle position contains the value we want. If it does, return true, we found our number in the array! If not, is the middle position higher than the searching value, if it is make a recursive call to our function, passing the search number, keep the low position bound and pass middle -1 as the high position bound. This is because we know the middle is higher than the search value, so the search value must be between the low and the middle positions. Else, if the two previous conditions are not true, we know the search number must be between the middle and the high position value so we pass the recursive call the search number, middle + 1 and the high value.<\/p>\n<p>This process then recursively repeats itself until it either narrows down the search range and finds the search value or it cycles through and never finds the search value. Below is the code demonstrating this process. Leave comments if you have any questions or improvements.<\/p>\n<div class=\"snippetcpt-wrap\" id=\"snippet-995\" data-id=\"995\" data-edit=\"\" data-copy=\"\/main\/wp-json\/wp\/v2\/posts\/994?snippet=17b1fac833&#038;id=995\" data-fullscreen=\"https:\/\/somethingk.com\/main\/code-snippets\/recursive-binary-search-in-c\/?full-screen=1\">\n\t\t\t\t<pre class=\"prettyprint linenums lang-c_cpp\" title=\"Recursive Binary Search in C++\">int sizeOfArray; \/\/size of array\r\nint* array; \/\/contains your array\r\n\r\nbool recursiveBinaryFind(int searchNum){\r\n    \/\/pass 0 as the low pasotion and the size of the array as the highest search range position\r\n    return recursiveBinaryFind(searchNum, 0, sizeOfArray);\r\n}\r\n\r\nbool recursiveBinaryFind(int searchNum, int lowBound, int highBound){\r\n    \/\/If the low position is greater than the high, quit we looped through everything and didn\\'t find our value\r\n    if (lowBound &gt; highBound)    return false;\r\n    \r\n    \/\/Find the middle position\r\n    int middle = (lowBound + highBound)\/2;\r\n\r\n    \/\/Did we find our value?\r\n    if (array[middle] == searchNum) {\r\n        return true;\r\n    } else if (array[middle] &gt; searchNum) {\r\n        \/\/Search the lower search range half\r\n        return recursiveBinaryFind(searchNum, lowBound, middle - 1);\r\n    } else {\r\n        \/\/Search the higher search range half\r\n        return recursiveBinaryFind(searchNum, middle + 1, highBound);\r\n    }\r\n}<\/pre>\n\t\t\t<\/div>\n","protected":false},"excerpt":{"rendered":"<p>I wrote a recursive binary find that looks through a sorted array for a given number. \u00a0(You can use this on an unsorted array, it just isn&#8217;t as performant.) This is how it works, the recursive function call requires the number to search and the lowest and highest positions\u00a0in a search range. To start, you give the low position, 0, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[177],"tags":[489,486,303,488,491,485,487,490],"class_list":["post-994","post","type-post","status-publish","format-standard","hentry","category-development","tag-array","tag-binary-search","tag-c","tag-find","tag-find-int","tag-recursive","tag-search","tag-search-array"],"_links":{"self":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/994","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/comments?post=994"}],"version-history":[{"count":1,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/994\/revisions"}],"predecessor-version":[{"id":996,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/994\/revisions\/996"}],"wp:attachment":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/media?parent=994"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/categories?post=994"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/tags?post=994"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}