{"id":24959,"date":"2017-10-15T13:54:41","date_gmt":"2017-10-15T08:24:41","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=24959"},"modified":"2017-10-15T13:54:41","modified_gmt":"2017-10-15T08:24:41","slug":"binary-search-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/binary-search-2\/","title":{"rendered":"Binary Search"},"content":{"rendered":"

 <\/p>\n

 <\/p>\n

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].<\/p>\n

A simple approach is to do linear search.The time complexity of above algorithm is O(n). Another approach to perform the same task is using Binary Search.<\/p>\n

Binary Search:<\/strong> Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.<\/p>\n

Example:<\/p>\n

\"Binary<\/p>\n

c and c++<\/p>\n[pastacode lang=”c” manual=”%23include%20%3Cstdio.h%3E%0A%20%0A%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%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%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%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%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%0A%20%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%20binarySearch(arr%2C%200%2C%20n-1%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%20result)%3B%0A%20%20%20return%200%3B%0A%7D” message=”c and c++” highlight=”” provider=”manual”\/]\n

Output<\/p>\n

Element is present at index 3<\/p>\n[ad type=”banner”]\n

Python<\/p>\n[pastacode lang=”python” manual=”%23%20Iterative%20Binary%20Search%20Function%0A%23%20It%20returns%20location%20of%20x%20in%20given%20array%20arr%20if%20present%2C%0A%23%20else%20returns%20-1%0Adef%20binarySearch(arr%2C%20l%2C%20r%2C%20x)%3A%0A%20%0A%20%20%20%20while%20l%20%3C%3D%20r%3A%0A%20%0A%20%20%20%20%20%20%20%20mid%20%3D%20l%20%2B%20(r%20-%20l)%2F2%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20x%20is%20present%20at%20mid%0A%20%20%20%20%20%20%20%20if%20arr%5Bmid%5D%20%3D%3D%20x%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20mid%0A%20%0A%20%20%20%20%20%20%20%20%23%20If%20x%20is%20greater%2C%20ignore%20left%20half%0A%20%20%20%20%20%20%20%20elif%20arr%5Bmid%5D%20%3C%20x%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20l%20%3D%20mid%20%2B%201%0A%20%0A%20%20%20%20%20%20%20%20%23%20If%20x%20is%20smaller%2C%20ignore%20right%20half%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20r%20%3D%20mid%20-%201%0A%20%20%20%20%20%0A%20%20%20%20%23%20If%20we%20reach%20here%2C%20then%20the%20element%20was%20not%20present%0A%20%20%20%20return%20-1%0A%20%0A%20%0A%23%20Test%20array%0Aarr%20%3D%20%5B%202%2C%203%2C%204%2C%2010%2C%2040%20%5D%0Ax%20%3D%2010%0A%20%0A%23%20Function%20call%0Aresult%20%3D%20binarySearch(arr%2C%200%2C%20len(arr)-1%2C%20x)%0A%20%0Aif%20result%20!%3D%20-1%3A%0A%20%20%20%20print%20%22Element%20is%20present%20at%20index%20%25d%22%20%25%20result%0Aelse%3A%0A%20%20%20%20print%20%22Element%20is%20not%20present%20in%20array%22%0A” message=”python” highlight=”” provider=”manual”\/]\n

Output<\/p>\n

Element is present at index 3<\/p>\n[ad type=”banner”]\n

Java<\/p>\n[pastacode lang=”java” manual=”%2F%2F%20Java%20implementation%20of%20iterative%20Binary%20Search%0Aclass%20BinarySearch%0A%7B%0A%20%20%20%20%2F%2F%20Returns%20index%20of%20x%20if%20it%20is%20present%20in%20arr%5B%5D%2C%20else%0A%20%20%20%20%2F%2F%20return%20-1%0A%20%20%20%20int%20binarySearch(int%20arr%5B%5D%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20l%20%3D%200%2C%20r%20%3D%20arr.length%20-%201%3B%0A%20%20%20%20%20%20%20%20while%20(l%20%3C%3D%20r)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20m%20%3D%20l%20%2B%20(r-l)%2F2%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20x%20is%20present%20at%20mid%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bm%5D%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20m%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20greater%2C%20ignore%20left%20half%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bm%5D%20%3C%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20l%20%3D%20m%20%2B%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20is%20smaller%2C%20ignore%20right%20half%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20r%20%3D%20m%20-%201%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20if%20we%20reach%20here%2C%20then%20element%20was%20not%20present%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%20to%20test%20above%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20BinarySearch%20ob%20%3D%20new%20BinarySearch()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B2%2C%203%2C%204%2C%2010%2C%2040%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20int%20x%20%3D%2010%3B%0A%20%20%20%20%20%20%20%20int%20result%20%3D%20ob.binarySearch(arr%2C%20x)%3B%0A%20%20%20%20%20%20%20%20if%20(result%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Element%20not%20present%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Element%20found%20at%20index%20%22%2Bresult)%3B%0A%20%20%20%20%7D%0A%7D” message=”java” highlight=”” provider=”manual”\/]\n

Output<\/p>\n

Element is present at index 3<\/p>\n[ad type=”banner”]\n

Time Complexity:<\/strong><\/p>\n

The time complexity of Binary Search can be written as<\/p>\n

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

The above recurrence can be solved either using Recurrence T ree method or Master method. It falls in case II of Master Method and solution of the recurrence is \"\\Theta(Logn)\".<\/p>\n

Auxiliary Space:<\/strong> O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space.<\/p>\n

Algorithmic Paradigm:<\/strong> Divide and Conquer.<\/p>\n","protected":false},"excerpt":{"rendered":"

Binary Search – search and sorting – Search a sorted array by dividing the search interval in half. Begin with an interval covering the whole array.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,1],"tags":[70276,70283,70319,70078,70096,70293,70289,70190,70299,70052,70264,70282,70304,70109,70076,70107,70120,70301,70081,70090,70082,70270,70113,70322,70088,70269,70309,70275,70295,70086,70265,70320,70321,70115,70307,70278,70297,70310,70263,70281,70279,70300,70284,70318,70277,70294,70098,70314,70305,70273,70316,70268,70287,70296,70303,70291,70288,70285,70312,70298,70311,70116,70028,70306,70271,63929,23950,70274,70290,70069,70063,70060,70262,70266,70286,70292,70272,62569,70099,70267,70280,70097,70315,70308,70261,70317,70026,23955,70302,70313],"class_list":["post-24959","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","category-coding","tag-algorithm-for-binary-search","tag-algorithm-of-binary-search","tag-applications-of-binary-search","tag-array-search","tag-arrays-binarysearch","tag-audio-search-engine","tag-balanced-binary-tree","tag-binary","tag-binary-compound","tag-binary-search","tag-binary-search-algorithm","tag-binary-search-algorithm-example","tag-binary-search-algorithm-in-c","tag-binary-search-algorithm-in-data-structure","tag-binary-search-c","tag-binary-search-c-program","tag-binary-search-code","tag-binary-search-code-in-c","tag-binary-search-complexity","tag-binary-search-definition","tag-binary-search-example","tag-binary-search-in-c","tag-binary-search-in-c-program","tag-binary-search-in-cpp","tag-binary-search-in-data-structure","tag-binary-search-in-java","tag-binary-search-in-python","tag-binary-search-java","tag-binary-search-java-program","tag-binary-search-program","tag-binary-search-program-in-c","tag-binary-search-program-in-c-using-function","tag-binary-search-program-in-cpp","tag-binary-search-program-in-data-structure","tag-binary-search-program-in-java","tag-binary-search-python","tag-binary-search-recursive-algorithm","tag-binary-search-time-complexity","tag-binary-search-tree","tag-binary-search-tree-algorithm","tag-binary-search-tree-example","tag-binary-search-tree-in-c","tag-binary-search-tree-in-data-structure","tag-binary-search-tree-insertion","tag-binary-search-tree-java","tag-binary-search-tree-program","tag-binary-search-using-recursion","tag-binary-search-using-recursion-in-c","tag-binary-semaphore","tag-binary-sort","tag-binary-sort-in-c","tag-binary-tree","tag-binary-tree-algorithm","tag-binary-tree-example","tag-binary-tree-in-c","tag-binary-tree-insertion","tag-binary-tree-java","tag-binary-tree-traversal","tag-binary-tree-vs-binary-search-tree","tag-bst-data-structure","tag-bst-tree","tag-c-program-for-binary-search","tag-complexity-of-binary-search","tag-complexity-of-binary-search-algorithm","tag-heap-sort","tag-image-search","tag-internet-search-engines","tag-java-binary-search","tag-java-program-for-binary-search","tag-linear-and-binary-search","tag-linear-search-and-binary-search","tag-linear-search-java","tag-merge-sort","tag-meta-search-engine","tag-program-for-binary-search","tag-recursive-binary-search-algorithm","tag-search-algorithms","tag-search-engine-marketing","tag-search-inc","tag-search-search","tag-search-tree","tag-searching-algorithms-in-c","tag-searching-algorithms-in-java","tag-searching-c","tag-seo","tag-the-complexity-of-binary-search-algorithm-is","tag-time-complexity-of-binary-search","tag-web-search-engines","tag-what-is-binary-search","tag-what-is-binary-search-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24959","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=24959"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24959\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=24959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=24959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=24959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}