{"id":25262,"date":"2017-10-15T16:25:51","date_gmt":"2017-10-15T10:55:51","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25262"},"modified":"2017-10-15T16:25:51","modified_gmt":"2017-10-15T10:55:51","slug":"problem-many-binary-search-implementations","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/problem-many-binary-search-implementations\/","title":{"rendered":"A Problem in Many Binary Search Implementations"},"content":{"rendered":"

Consider the following C implementation of Binary Search function, is there anything wrong in this?<\/p>\n

c<\/span> <\/div> 
\/\/ A iterative binary search function. It returns location of x in\/\/ given array arr[l..r] if present, otherwise -1int binarySearch(int arr[], int l, int r, int x){    while (l <= r)    {        \/\/ find index of middle element        int m = (l+r)\/2;         \/\/ Check if x is present at mid        if (arr[m] == x) return m;         \/\/ If x greater, ignore left half        if (arr[m] < x) l = m + 1;         \/\/ If x is smaller, ignore right half        else r = m - 1;    }     \/\/ if we reach here, then element was not present    return -1;}<\/code><\/pre> <\/div>\n
The above looks fine except one subtle thing, the expression \u201cm = (l+r)\/2\u201d. It fails for large values of l and r. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (231<\/sup>\u2013 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results.<\/p>\n[ad type=”banner”]\n
What is the way to resolve this problem?<\/strong>
\nFollowing is one way:<\/p>\n
        int mid = low + ((high - low) \/ 2);<\/pre>\n
Probably faster, and arguably as clear is (works only in Java, refer this):<\/p>\n
        int mid = (low + high) >>> 1;<\/pre>\n
In C and C++ (where you don\u2019t have the >>> operator), you can do this:<\/p>\n
        mid = ((unsigned int)low + (unsigned int)high)) >> 1<\/pre>\n
The similar problem appears in Merge Sort as well.<\/p>\n
The above content is taken from google reasearch blog.<\/p>\n
Please refer this as well, it points out that the above solutions may not always work.<\/p>\n
The above problem occurs when array length is 230<\/sup> or greater and the search repeatedly moves to second half of the array. This much size of array is not likely to appear most of the time. For example, when we try the below program with 32 bit Code Blocks compiler, we get compiler error.<\/p>\n[ad type=”banner”]\n
 
 c<\/span> <\/div> 
int main(){    int arr[1<<30];    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
error: size of array 'arr' is too large<\/pre>\n
Even when we try boolean array, the program compiles fine, but crashes when run in Windows 7.0 and Code Blocks 32 bit compiler<\/p>\n
 
 c<\/span> <\/div> 
#include <stdbool.h>int main(){    bool arr[1<<30];    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
No compiler error, but crashes at run time.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
A Problem in Many Binary Search Implementations – Searching and Sorting – The above looks fine except one subtle thing, the expression \u201cm = (l+r)\/2\u201d. It fails for large values of l and r. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (231\u2013 1).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,82509,71670],"tags":[72674,70276,70283,70078,70096,72678,70052,70264,70282,72682,72680,70076,70120,70081,70082,70275,70086,72693,70278,70310,70263,70281,72684,70279,72676,70284,70277,72694,70273,70268,70287,72683,72675,70288,72689,70285,72677,72688,72690,70028,72692,70274,72687,72685,70286,72681,72691,70280,72686,72679,70026],"class_list":["post-25262","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-binary-search-tree-2","category-searching-and-sorting","tag-a-problem-in-many-binary-search-implementations","tag-algorithm-for-binary-search","tag-algorithm-of-binary-search","tag-array-search","tag-arrays-binarysearch","tag-binary-algorithm","tag-binary-search","tag-binary-search-algorithm","tag-binary-search-algorithm-example","tag-binary-search-algorithm-java","tag-binary-search-array-c","tag-binary-search-c","tag-binary-search-code","tag-binary-search-complexity","tag-binary-search-example","tag-binary-search-java","tag-binary-search-program","tag-binary-search-pseudocode","tag-binary-search-python","tag-binary-search-time-complexity","tag-binary-search-tree","tag-binary-search-tree-algorithm","tag-binary-search-tree-code-c","tag-binary-search-tree-example","tag-binary-search-tree-implementation-c","tag-binary-search-tree-in-data-structure","tag-binary-search-tree-java","tag-binary-search-tree-program-in-data-structure-using-c","tag-binary-sort","tag-binary-tree","tag-binary-tree-algorithm","tag-binary-tree-c","tag-binary-tree-in-data-structure","tag-binary-tree-java","tag-binary-tree-search","tag-binary-tree-traversal","tag-c-binary-search-algorithm","tag-c-binary-tree","tag-c-binary-search","tag-complexity-of-binary-search","tag-example-of-binary","tag-java-binary-search","tag-java-binary-search-tree","tag-java-binary-tree","tag-program-for-binary-search","tag-python-binary-search","tag-recursive-binary-search","tag-search-tree","tag-searching-algorithms-c","tag-simple-binary-search-tree-program-in-c","tag-time-complexity-of-binary-search"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25262","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=25262"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25262\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25262"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25262"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25262"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}