{"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

C++<\/span> <\/div> 
\/\/ A recursive binary search function. It returns location of x in\/\/ given array arr[l..r] is present, otherwise -1int binarySearch(int arr[], int l, int r, int x){   if (r >= l)   {        int mid = l + (r - l)\/2;          \/\/ If the element is present at the middle itself        if (arr[mid] == x)  return mid;          \/\/ If element is smaller than mid, then it can only be present        \/\/ in left subarray        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);          \/\/ Else the element can only be present in right subarray        return binarySearch(arr, mid+1, r, x);   }     \/\/ We reach here when element is not present in array   return -1;} <\/code><\/pre> <\/div>\n
 <\/p>\n
The following is a simple recursive Ternary Search<\/strong> function in C++.<\/p>\n
 
 C++<\/span> <\/div> 
\/\/ A recursive ternary search function. It returns location of x in\/\/ given array arr[l..r] is present, otherwise -1int ternarySearch(int arr[], int l, int r, int x){   if (r >= l)   {        int mid1 = l + (r - l)\/3;        int mid2 = mid1 + (r - l)\/3;         \/\/ If x is present at the mid1        if (arr[mid1] == x)  return mid1;         \/\/ If x is present at the mid2        if (arr[mid2] == x)  return mid2;         \/\/ If x is present in left one-third        if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);         \/\/ If x is present in right one-third        if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);         \/\/ If x is present in middle one-third        return ternarySearch(arr, mid1+1, mid2-1, x);   }   \/\/ We reach here when element is not present in array   return -1;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\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=”banner”]\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}]}}