## Sunday, March 09, 2008

### Binary search

Today I want to discuss about the binary search algorithm.

Binary search algorithm is generally used for searching a key in a sorted list.

There are three different variation of this algorithm available. In this algorithm I would be explaining the first variation.

The pseudo code of this algorithm would look like

`BinarySearch (Array[0..N-1], key){ low = 0 high = N-1 while (low <= high) { mid = (low + high) / 2 if (Array[mid] > key) high = mid - 1 else if (Array[mid] < key) low = mid + 1 else return mid // key present at Array[mid] } return -1 // not found}`

The C program would look like

```/* * int binary_search(int array[], int size, int key) * * @param array sorted array of integer * @param size the size of the array * @param key the search element * * @return if search is successful, position of key is returned * else -1 * * @desc int binary_search ```
``` Posted by Raghu Nayak at 7:07:00 PM Labels: Algorithms, C Language, programs Email ThisBlogThis!Share to TwitterShare to FacebookShare to Pinterest ```
``` No comments: Post a Comment ```
``` ```
``` ```
``` Newer Post Older Post Home Subscribe to: Post Comments (Atom) ```
``` ```
``` ```
``` Search This Blog About Me Raghu Nayak View my complete profile (adsbygoogle = window.adsbygoogle || []).push({}); Subscribe To Posts Comments Total Hits My other websites RaghuNayak's blog My Review of Vested Finance - Invest in US stocks from India/Australia 2 years ago Labels Linux (32) God (25) How To (22) Experiments (17) News (17) Development (16) Fun (14) Windows (14) Internet-News (13) Qt (12) Airtel (11) Ubuntu (11) Blogging (10) Open Source (10) Tutorial (10) Apple (9) Site-News (9) Tips (9) Wishes (9) Broadband (8) Hacks (8) Microsoft (8) Wallpapers (8) Algorithms (7) C Language (7) GNOME (7) Google (7) Internet (7) programs (7) FOSS (6) Hardware (5) Mac OS (5) Personal News (5) Sample Code (5) FSF (4) MIT License (4) Mac (4) Videos (4) Blogger (3) C++ (3) Design-Pattern (3) Linux-News (3) Programming (3) Rants (3) Applications (2) CMake (2) Downloads (2) KDE4 (2) OOP (2) Security (2) Site Info (2) Solaris (2) Tech Recipes (2) Twitter (2) WTF? (2) Audiophile (1) Automation (1) CentOS (1) Chrome (1) Conan (1) Fedora (1) GPLv3 (1) Go Green (1) NBN (1) Questionnaire (1) Ruby (1) SF.net (1) Shell (1) Testing (1) Themes (1) Unix (1) Web (1) Wishea (1) YouTube (1) Blog Archive Blog Archive Sep 2022 (1) Mar 2022 (1) May 2021 (3) Apr 2021 (1) Mar 2021 (4) Jul 2020 (9) Nov 2017 (1) Dec 2016 (1) Nov 2016 (4) May 2016 (1) Jul 2015 (4) Aug 2014 (1) Dec 2013 (1) Nov 2013 (1) Jun 2013 (1) Jan 2012 (1) Dec 2011 (1) Oct 2011 (2) Jul 2011 (1) Apr 2011 (5) Mar 2011 (1) Dec 2010 (3) Aug 2010 (2) Apr 2010 (2) Feb 2010 (4) Jan 2010 (1) Dec 2009 (1) Nov 2009 (2) Oct 2009 (3) Aug 2009 (1) Jul 2009 (2) Jun 2009 (1) May 2009 (4) Apr 2009 (15) Mar 2009 (13) Feb 2009 (2) Jan 2009 (1) Oct 2008 (1) Jul 2008 (4) Jun 2008 (1) May 2008 (6) Apr 2008 (9) Mar 2008 (9) Feb 2008 (3) Jan 2008 (8) Dec 2007 (3) Nov 2007 (4) Oct 2007 (3) Sep 2007 (2) Aug 2007 (1) Jul 2007 (1) May 2007 (6) Apr 2007 (1) Mar 2007 (5) Dec 2006 (2) Nov 2006 (1) Oct 2006 (2) Jan 2006 (1) _gos='monster.gostats.com';_goa=400292; _got=5;_goi=1;_gol='web page statistics';_GoStatsRun(); var sc_project=2345784; var sc_invisible=1; var sc_security="2e9ccdee"; Currently cooking.. new TWTR.Widget({ version: 2, type: 'profile', rpp: 4, interval: 6000, width: 200, height: 200, theme: { shell: { background: '#366fc9', color: '#bcc9dc' }, tweets: { background: '#dde8f3', color: '#2b2b2b', links: '#105294' } }, features: { scrollbar: true, loop: false, live: true, hashtags: true, timestamp: true, avatars: false, behavior: 'all' } }).render().setUser('openguru').start(); ```
``` ```
``` ```
``` ```
``` ```
``` Popular Posts How To: Fix mfc100u.dll missing in Windows Solution is simple. If you have 64bit Windows system, install Microsoft Visual C++ 2010 SP1 Redistributable package - 64bit version . I... CMake: Detecting Platform/Operating Systems, Compiler Information I was searching for this information from last three days. Finally I found the CMake syntax to write the platform specific code inside CMake... var _gaq = _gaq || []; _gaq.push(['_setAccount', 'UA-991414-1']); _gaq.push(['_trackPageview']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })(); © 2020 Raghu Nayak. Theme images by Jason Morrow. Powered by Blogger. ```
``` ```
``` ```
``` ```
``` window.setTimeout(function() { document.body.className = document.body.className.replace('loading', ''); }, 10); window['__wavt'] = 'AOuZoY4wHqrQHx6jXySRjNsjrkgOmmaEDw:1685908852486';_WidgetManager._Init('//www.blogger.com/rearrange?blogID\x3d34127924','//www.openguru.com/2008/03/binary-search.html','34127924'); _WidgetManager._SetDataContext([{'name': 'blog', 'data': {'blogId': '34127924', 'title': 'OpenGuru Weblog', 'url': 'https://www.openguru.com/2008/03/binary-search.html', 'canonicalUrl': 'https://www.openguru.com/2008/03/binary-search.html', 'homepageUrl': 'https://www.openguru.com/', 'searchUrl': 'https://www.openguru.com/search', 'canonicalHomepageUrl': 'https://www.openguru.com/', 'blogspotFaviconUrl': 'https://www.openguru.com/favicon.ico', 'bloggerUrl': 'https://www.blogger.com', 'hasCustomDomain': true, 'httpsEnabled': true, 'enabledCommentProfileImages': true, 'gPlusViewType': 'FILTERED_POSTMOD', 'adultContent': false, 'analyticsAccountNumber': '', 'encoding': 'UTF-8', 'locale': 'en', 'localeUnderscoreDelimited': 'en', 'languageDirection': 'ltr', 'isPrivate': false, 'isMobile': false, 'isMobileRequest': false, 'mobileClass': '', 'isPrivateBlog': false, 'isDynamicViewsAvailable': true, 'feedLinks': '\x3clink rel\x3d\x22alternate\x22 type\x3d\x22application/atom+xml\x22 title\x3d\x22OpenGuru Weblog - Atom\x22 href\x3d\x22https://www.openguru.com/feeds/posts/default\x22 /\x3e\n\x3clink rel\x3d\x22alternate\x22 type\x3d\x22application/rss+xml\x22 title\x3d\x22OpenGuru Weblog - RSS\x22 href\x3d\x22https://www.openguru.com/feeds/posts/default?alt\x3drss\x22 /\x3e\n\x3clink rel\x3d\x22service.post\x22 type\x3d\x22application/atom+xml\x22 title\x3d\x22OpenGuru Weblog - Atom\x22 href\x3d\x22https://www.blogger.com/feeds/34127924/posts/default\x22 /\x3e\n\n\x3clink rel\x3d\x22alternate\x22 type\x3d\x22application/atom+xml\x22 title\x3d\x22OpenGuru Weblog - Atom\x22 href\x3d\x22https://www.openguru.com/feeds/1126890375643519286/comments/default\x22 /\x3e\n', 'meTag': '', 'adsenseClientId': 'ca-pub-5128912746589006', 'adsenseHostId': 'ca-host-pub-1556223355139109', 'adsenseHasAds': true, 'adsenseAutoAds': false, 'boqCommentIframeForm': true, 'loginRedirectParam': '', 'view': '', 'dynamicViewsCommentsSrc': '//www.blogblog.com/dynamicviews/4224c15c4e7c9321/js/comments.js', 'dynamicViewsScriptSrc': '//www.blogblog.com/dynamicviews/0942d4f782c66904', 'plusOneApiSrc': 'https://apis.google.com/js/platform.js', 'disableGComments': true, 'sharing': {'platforms': [{'name': 'Get link', 'key': 'link', 'shareMessage': 'Get link', 'target': ''}, {'name': 'Facebook', 'key': 'facebook', 'shareMessage': 'Share to Facebook', 'target': 'facebook'}, {'name': 'BlogThis!', 'key': 'blogThis', 'shareMessage': 'BlogThis!', 'target': 'blog'}, {'name': 'Twitter', 'key': 'twitter', 'shareMessage': 'Share to Twitter', 'target': 'twitter'}, {'name': 'Pinterest', 'key': 'pinterest', 'shareMessage': 'Share to Pinterest', 'target': 'pinterest'}, {'name': 'Email', 'key': 'email', 'shareMessage': 'Email', 'target': 'email'}], 'disableGooglePlus': true, 'googlePlusShareButtonWidth': 0, 'googlePlusBootstrap': '\x3cscript type\x3d\x22text/javascript\x22\x3ewindow.___gcfg \x3d {\x27lang\x27: \x27en\x27};\x3c/script\x3e'}, 'hasCustomJumpLinkMessage': false, 'jumpLinkMessage': 'Read more', 'pageType': 'item', 'postId': '1126890375643519286', 'pageName': 'Binary search', 'pageTitle': 'OpenGuru Weblog: Binary search', 'metaDescription': ''}}, {'name': 'features', 'data': {}}, {'name': 'messages', 'data': {'edit': 'Edit', 'linkCopiedToClipboard': 'Link copied to clipboard!', 'ok': 'Ok', 'postLink': 'Post Link'}}, {'name': 'template', 'data': {'name': 'custom', 'localizedName': 'Custom', 'isResponsive': false, 'isAlternateRendering': false, 'isCustom': true}}, {'name': 'view', 'data': {'classic': {'name': 'classic', 'url': '?view\x3dclassic'}, 'flipcard': {'name': 'flipcard', 'url': '?view\x3dflipcard'}, 'magazine': {'name': 'magazine', 'url': '?view\x3dmagazine'}, 'mosaic': {'name': 'mosaic', 'url': '?view\x3dmosaic'}, 'sidebar': {'name': 'sidebar', 'url': '?view\x3dsidebar'}, 'snapshot': {'name': 'snapshot', 'url': '?view\x3dsnapshot'}, 'timeslide': {'name': 'timeslide', 'url': '?view\x3dtimeslide'}, 'isMobile': false, 'title': 'Binary search', 'description': '', 'url': 'https://www.openguru.com/2008/03/binary-search.html', 'type': 'item', 'isSingleItem': true, 'isMultipleItems': false, 'isError': false, 'isPage': false, 'isPost': true, 'isHomepage': false, 'isArchive': false, 'isLabelSearch': false, 'postId': 1126890375643519286}}]); _WidgetManager._RegisterWidget('_NavbarView', new _WidgetInfo('Navbar1', 'navbar', document.getElementById('Navbar1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HeaderView', new _WidgetInfo('Header1', 'header', document.getElementById('Header1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_PageListView', new _WidgetInfo('PageList1', 'crosscol', document.getElementById('PageList1'), {'title': 'Pages', 'links': [{'isCurrentPage': false, 'href': 'https://www.openguru.com/', 'title': 'Home'}, {'isCurrentPage': false, 'href': 'https://www.openguru.com/p/open-source.html', 'id': '4946848894023073997', 'title': 'Open Source'}, {'isCurrentPage': false, 'href': 'https://www.openguru.com/p/subscribe-us.html', 'id': '2470836024367484782', 'title': 'Subscribe'}, {'isCurrentPage': false, 'href': 'https://www.openguru.com/p/contact.html', 'id': '1638023654640918060', 'title': 'Contact Me'}, {'isCurrentPage': false, 'href': 'https://www.openguru.com/p/aboutus.html', 'id': '1648337132402685970', 'title': 'About..'}], 'mobile': false}, 'displayModeFull')); _WidgetManager._RegisterWidget('_BlogView', new _WidgetInfo('Blog1', 'main', document.getElementById('Blog1'), {'cmtInteractionsEnabled': false, 'lightboxEnabled': true, 'lightboxModuleUrl': 'https://www.blogger.com/static/v1/jsbin/2226058792-lbx.js', 'lightboxCssUrl': 'https://www.blogger.com/static/v1/v-css/3268905543-lightbox_bundle.css'}, 'displayModeFull')); _WidgetManager._RegisterWidget('_BlogSearchView', new _WidgetInfo('BlogSearch1', 'sidebar-right-1', document.getElementById('BlogSearch1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_ProfileView', new _WidgetInfo('Profile1', 'sidebar-right-1', document.getElementById('Profile1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HTMLView', new _WidgetInfo('HTML5', 'sidebar-right-1', document.getElementById('HTML5'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_AdSenseView', new _WidgetInfo('AdSense1', 'sidebar-right-1', document.getElementById('AdSense1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_SubscribeView', new _WidgetInfo('Subscribe1', 'sidebar-right-1', document.getElementById('Subscribe1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_StatsView', new _WidgetInfo('Stats1', 'sidebar-right-1', document.getElementById('Stats1'), {'title': 'Total Hits', 'showGraphicalCounter': false, 'showAnimatedCounter': true, 'showSparkline': false, 'statsUrl': '//www.openguru.com/b/stats?style\x3dBLACK_TRANSPARENT\x26timeRange\x3dALL_TIME\x26token\x3dAPq4FmAsljA6FUgvd4vnxiRZXZCa4qRMClxYbQvsFitCgeif3nFAz4UsiKAiIcw4dVBmkBHYmnuKdEWxSlzPUIvzLA7TJOUpow'}, 'displayModeFull')); _WidgetManager._RegisterWidget('_BlogListView', new _WidgetInfo('BlogList1', 'sidebar-right-1', document.getElementById('BlogList1'), {'numItemsToShow': 0, 'totalItems': 1}, 'displayModeFull')); _WidgetManager._RegisterWidget('_LabelView', new _WidgetInfo('Label1', 'sidebar-right-1', document.getElementById('Label1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_BlogArchiveView', new _WidgetInfo('BlogArchive1', 'sidebar-right-1', document.getElementById('BlogArchive1'), {'languageDirection': 'ltr', 'loadingMessage': 'Loading\x26hellip;'}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HTMLView', new _WidgetInfo('HTML4', 'sidebar-right-1', document.getElementById('HTML4'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HTMLView', new _WidgetInfo('HTML3', 'sidebar-right-1', document.getElementById('HTML3'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_PopularPostsView', new _WidgetInfo('PopularPosts1', 'footer-1', document.getElementById('PopularPosts1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HTMLView', new _WidgetInfo('HTML1', 'footer-1', document.getElementById('HTML1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HTMLView', new _WidgetInfo('HTML2', 'footer-2-2', document.getElementById('HTML2'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_AttributionView', new _WidgetInfo('Attribution1', 'footer-3', document.getElementById('Attribution1'), {}, 'displayModeFull')); ```