{"id":24947,"date":"2017-10-15T13:58:56","date_gmt":"2017-10-15T08:28:56","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=24947"},"modified":"2017-10-15T13:58:56","modified_gmt":"2017-10-15T08:28:56","slug":"ternary-search","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/ternary-search\/","title":{"rendered":"TERNARY SEARCH"},"content":{"rendered":"

Why is Binary Search preferred over Ternary Search?<\/h1>\n

The following is a simple recursive Binary Search<\/strong> function in C++ taken<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20recursive%20binary%20search%20function.%20It%20returns%20location%20of%20x%20in%0A%2F%2F%20given%20array%20arr%5Bl..r%5D%20is%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%20if%20(r%20%3E%3D%20l)%0A%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%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20element%20is%20present%20at%20the%20middle%20itself%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3D%3D%20x)%20%20return%20mid%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20element%20is%20smaller%20than%20mid%2C%20then%20it%20can%20only%20be%20present%0A%20%20%20%20%20%20%20%20%2F%2F%20in%20left%20subarray%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3E%20x)%20return%20binarySearch(arr%2C%20l%2C%20mid-1%2C%20x)%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Else%20the%20element%20can%20only%20be%20present%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%7D%0A%20%20%0A%20%20%20%2F%2F%20We%20reach%20here%20when%20element%20is%20not%20present%20in%20array%0A%20%20%20return%20-1%3B%0A%7D%20\u2033 message=\u201dC++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

\u00a0<\/p>\n

The following is a simple recursive Ternary Search<\/strong> function in C++.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20recursive%20ternary%20search%20function.%20It%20returns%20location%20of%20x%20in%0A%2F%2F%20given%20array%20arr%5Bl..r%5D%20is%20present%2C%20otherwise%20-1%0Aint%20ternarySearch(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r%2C%20int%20x)%0A%7B%0A%20%20%20if%20(r%20%3E%3D%20l)%0A%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20mid1%20%3D%20l%20%2B%20(r%20-%20l)%2F3%3B%0A%20%20%20%20%20%20%20%20int%20mid2%20%3D%20mid1%20%2B%20(r%20-%20l)%2F3%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20is%20present%20at%20the%20mid1%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid1%5D%20%3D%3D%20x)%20%20return%20mid1%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20is%20present%20at%20the%20mid2%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid2%5D%20%3D%3D%20x)%20%20return%20mid2%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20is%20present%20in%20left%20one-third%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid1%5D%20%3E%20x)%20return%20ternarySearch(arr%2C%20l%2C%20mid1-1%2C%20x)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20is%20present%20in%20right%20one-third%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid2%5D%20%3C%20x)%20return%20ternarySearch(arr%2C%20mid2%2B1%2C%20r%2C%20x)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20is%20present%20in%20middle%20one-third%0A%20%20%20%20%20%20%20%20return%20ternarySearch(arr%2C%20mid1%2B1%2C%20mid2-1%2C%20x)%3B%0A%20%20%20%7D%0A%20%20%20%2F%2F%20We%20reach%20here%20when%20element%20is%20not%20present%20in%20array%0A%20%20%20return%20-1%3B%0A%7D\u201d message=\u201dC++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n

Which of the above two does less comparisons in worst case?<\/strong><\/p>\n

From the first look, it seems the ternary search does less number of comparisons as it makes Log3<\/sub>n recursive calls, but binary search makes Log2<\/sub>n recursive calls. Let us take a closer look.
\nThe following is recursive formula for counting comparisons in worst case of Binary Search.<\/p>\n

T(n) = T(n\/2) + 2, T(1) = 1<\/p>\n

The following is recursive formula for counting comparisons in worst case of Ternary Search.<\/p>\n

T(n) = T(n\/3) + 4, T(1) = 1<\/p>\n

In binary search, there are 2Log2<\/sub>n + 1 comparisons in worst case. In ternary search, there are 4Log3<\/sub>n + 1 comparisons in worst case.<\/p>\n

Time Complexity for Binary search = 2clog2<\/sub>n + O(1)<\/p>\n

Time Complexity for Ternary search = 4clog3<\/sub>n + O(1)<\/p>\n

Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log3<\/sub>n and Log2<\/sub>n . The value of 2Log3<\/sub>n can be written as (2 \/ Log2<\/sub>3) * Log2<\/sub>n . Since the value of (2 \/ Log2<\/sub>3) is more than one, Ternary Search does more comparisons than Binary Search in worst case.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"

TERNARY SEARCH – searching and sorting algorithm – The ternary search does less number of comparisons as it makes Log3n recursive calls, but binary search.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[82509,1,71670],"tags":[70276,70283,70664,70052,70264,70111,70669,7378,70660,70667,70656,70651,70665,70649,70658,70292,70272,70670,70099,70668,70671,70280,70097,70315,70308,70072,70652,70653,70666,70659,70654,70655,70650,70663,70657,70662,70661],"class_list":["post-24947","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree-2","category-coding","category-searching-and-sorting","tag-algorithm-for-binary-search","tag-algorithm-of-binary-search","tag-balanced-search-tree","tag-binary-search","tag-binary-search-algorithm","tag-binary-search-topcoder","tag-binary-search-tree-applications","tag-c-string","tag-data-structure-tree","tag-data-structures-geeksforgeeks","tag-grams-search-engine","tag-java-test","tag-multiway-search-tree","tag-optimization","tag-radix-tree","tag-recursive-binary-search-algorithm","tag-search-algorithms","tag-search-function","tag-search-inc","tag-search-protect","tag-search-string","tag-search-tree","tag-searching-algorithms-in-c","tag-searching-algorithms-in-java","tag-searching-c","tag-searching-in-data-structure","tag-sorting-algorithms-in-c","tag-spelling-test","tag-string-sorting-in-c","tag-ternary","tag-ternary-search","tag-ternary-search-tree","tag-tree-data-structure","tag-tree-data-structure-in-c","tag-tree-java","tag-trees-inc","tag-trie-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24947","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=24947"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24947\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=24947"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=24947"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=24947"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}