{"id":25035,"date":"2017-10-15T14:03:08","date_gmt":"2017-10-15T08:33:08","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25035"},"modified":"2018-10-25T16:22:10","modified_gmt":"2018-10-25T10:52:10","slug":"exponential-search","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/exponential-search\/","title":{"rendered":"Exponential Search"},"content":{"rendered":"<p>The name of this searching algorithm may be misleading as it works in<strong> O(Log n)<\/strong> time. The name comes from the way it searches an element.<\/p>\n<h3 id=\"given-a-sorted-array-an-element-x-to-be-searched-find-position-of-x-in-the-array\"><span style=\"color: #ff6600;\">Given a sorted array an element x to be searched, find position of x in the array:<\/span><\/h3>\n<p><span style=\"color: #800000;\"><strong>Input:<\/strong><\/span> arr[ ] = {10, 20, 40, 45, 55} x = 45<\/p>\n<p><span style=\"color: #008080;\"><strong>Output:<\/strong><\/span> Element found at index 3<\/p>\n<p><span style=\"color: #800000;\"><strong>Input:<\/strong><\/span> arr[ ] = {10, 15, 25, 45, 55} x = 15<\/p>\n<p><span style=\"color: #008080;\"><strong>Output:<\/strong> <\/span>Element found at index 1<\/p>\n<h3 id=\"exponential-search-involves-two-steps\"><span style=\"color: #800080;\">Exponential search involves two steps:<\/span><\/h3>\n<ol>\n<li>Find range where element is present<\/li>\n<li>Do <a href=\"https:\/\/www.wikitechy.com\/technology\/c-programming-binary-tree-vertical-order-hashmap-based-method\/\">Binary Search<\/a> in above found range.<\/li>\n<\/ol>\n[ad type=\u201dbanner\u201d]\n<h3 id=\"how-to-find-the-range-where-element-may-be-present\"><span style=\"color: #339966;\"><strong>How to find the range where element may be present?<\/strong><\/span><\/h3>\n<p>The idea is to start with <a href=\"https:\/\/www.wikitechy.com\/technology\/cc-programming-maximum-of-all-subarrays-of-size-k\/\">sub-array<\/a> size 1 compare its last element with x, then try size 2, then 4 and so on until last element of a sub-array is not greater.<br \/>\nOnce we find an index i (after repeated doubling of i), we know that the element must be present between i\/2 and i (Why i\/2? because we could not find a greater value in previous iteration)<\/p>\n<h3 id=\"c-implementation\"><span style=\"color: #993366;\">C++ Implementation:<\/span><\/h3>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20an%20element%20x%20in%20a%0A%2F%2F%20sorted%20array%20using%20Exponential%20search.%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Aint%20binarySearch(int%20arr%5B%5D%2C%20int%2C%20int%2C%20int)%3B%0A%20%0A%2F%2F%20Returns%20position%20of%20first%20ocurrence%20of%0A%2F%2F%20x%20in%20array%0Aint%20exponentialSearch(int%20arr%5B%5D%2C%20int%20n%2C%20int%20x)%0A%7B%0A%20%20%20%20%2F%2F%20If%20x%20is%20present%20at%20firt%20location%20itself%0A%20%20%20%20if%20(arr%5B0%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Find%20range%20for%20binary%20search%20by%0A%20%20%20%20%2F%2F%20repeated%20doubling%0A%20%20%20%20int%20i%20%3D%201%3B%0A%20%20%20%20while%20(i%20%3C%20n%20%26%26%20arr%5Bi%5D%20%3C%3D%20x)%0A%20%20%20%20%20%20%20%20i%20%3D%20i*2%3B%0A%20%0A%20%20%20%20%2F%2F%20%20Call%20binary%20search%20for%20the%20found%20range.%0A%20%20%20%20return%20binarySearch(arr%2C%20i%2F2%2C%20min(i%2C%20n)%2C%20x)%3B%0A%7D%0A%20%0A%2F%2F%20A%20recursive%20binary%20search%20function.%20It%20returns%0A%2F%2F%20location%20of%20x%20in%20%20given%20array%20arr%5Bl..r%5D%20is%0A%2F%2F%20present%2C%20otherwise%20-1%0Aint%20binarySearch(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r%2C%20int%20x)%0A%7B%0A%20%20%20%20if%20(r%20%3E%3D%20l)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20mid%20%3D%20l%20%2B%20(r%20-%20l)%2F2%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20element%20is%20present%20at%20the%20middle%0A%20%20%20%20%20%20%20%20%2F%2F%20itself%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20mid%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20element%20is%20smaller%20than%20mid%2C%20then%20it%0A%20%20%20%20%20%20%20%20%2F%2F%20can%20only%20be%20present%20n%20left%20subarray%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3E%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20binarySearch(arr%2C%20l%2C%20mid-1%2C%20x)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Else%20the%20element%20can%20only%20be%20present%0A%20%20%20%20%20%20%20%20%2F%2F%20in%20right%20subarray%0A%20%20%20%20%20%20%20%20return%20binarySearch(arr%2C%20mid%2B1%2C%20r%2C%20x)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20We%20reach%20here%20when%20element%20is%20not%20present%0A%20%20%20%20%2F%2F%20in%20array%0A%20%20%20%20return%20-1%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20code%0Aint%20main(void)%0A%7B%0A%20%20%20int%20arr%5B%5D%20%3D%20%7B2%2C%203%2C%204%2C%2010%2C%2040%7D%3B%0A%20%20%20int%20n%20%3D%20sizeof(arr)%2F%20sizeof(arr%5B0%5D)%3B%0A%20%20%20int%20x%20%3D%2010%3B%0A%20%20%20int%20result%20%3D%20exponentialSearch(arr%2C%20n%2C%20x)%3B%0A%20%20%20(result%20%3D%3D%20-1)%3F%20printf(%22Element%20is%20not%20present%20in%20array%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3A%20printf(%22Element%20is%20present%20at%20index%20%25d%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result)%3B%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dc++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #008000;\">Output :<\/span><\/h3>\n[pastacode lang=\u201dcpp\u201d manual=\u201dElement%20is%20present%20at%20index%203\u2033 message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Time Complexity : <\/strong>O(Log n)<br \/>\n<strong>Auxiliary Space :<\/strong> The above implementation of Binary Search is recursive and requires O(Log n) space. With iterative Binary Search, we need only O(1) space.<\/p>\n<h3 id=\"applications-of-exponential-search\"><span style=\"color: #0000ff;\"><strong>Applications of Exponential Search:<\/strong><\/span><\/h3>\n<ol>\n<li>Exponential Binary Search is particularly useful for unbounded searches, where size of <a href=\"https:\/\/www.wikitechy.com\/technology\/c-programming-check-array-can-divided-pairs-whose-sum-divisible-k\/\">array<\/a> is infinite. Please refer <a href=\"http:\/\/www.geeksforgeeks.org\/find-the-point-where-a-function-becomes-negative\/\">Unbounded Binary Search<\/a> for an example.<\/li>\n<li>It works better than Binary Search for bounded arrays also when the element to be searched is closer to the first element.<\/li>\n<\/ol>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Exponential Search &#8211; searching and sorting algorithm &#8211; The name of this searching algorithm may be misleading as it works in O(Log n) time.<\/p>\n","protected":false},"author":1,"featured_media":31432,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[82509,1,71670],"tags":[70052,70935,70750,70941,70946,70956,70940,70262,70938,70957,70944,70953,70937,70949,70952,70951,70955,70947,70954,6910,70939,3588,70936,70945,70950,70934,70948],"class_list":["post-25035","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-binary-search-tree-2","category-coding","category-searching-and-sorting","tag-binary-search","tag-canada-wiki","tag-exponential","tag-exponential-growth","tag-exponi-watch","tag-indonesia-wiki","tag-java-regex","tag-merge-sort","tag-merge-sort-in-c","tag-perl-regular-expression","tag-php-regex","tag-python-re","tag-python-regex","tag-python-regex-example","tag-python-regular-expression","tag-re-python","tag-regex-expression","tag-regex-php","tag-regex-python","tag-regular-expression","tag-regular-expression-in-java","tag-regular-expression-in-php","tag-regular-expression-in-python","tag-regular-expression-php","tag-regular-expression-python","tag-wikipedia-india","tag-wikipedia-singapore"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25035","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=25035"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25035\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31432"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25035"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25035"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25035"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}