Monday, July 9, 2007

Write C code to implement the Binary Search algorithm.

Here is a C function


int binarySearch(int arr[],int size, int item)
{
int left, right, middle;
left = 0;
right = size-1;

while(left <= right)
{
middle = ((left + right)/2);

if(item == arr[middle])
{
return(middle);
}

if(item > arr[middle])
{
left = middle+1;
}
else
{
right = middle-1;
}
}

return(-1);
}



Note that the Binary Search algorithm has a prerequisite that the array passed to it must be already sorted in ascending order. This will not work on an unsorted array. The complexity of this algorithm is O(log(n)).

45 comments:

Anonymous said...

This code suffers from the usual problems of seemingly straightforward implementations of binary search: two instead of one comparisons inside the loop and problems with integer overflows for large arrays.

The following code I believe to be more robust and efficient (if you don't have C++/templates, just replace keyType with whatever is needed):

template<typename keyType> size_t binarySearch (keyType* s, size_t h, keyType n) {
if (h) {
size_t l=0;
while (l < h) {
size_t m = l + (h-l) / 2;
if (s [m] < n) {
l = m + 1;
} else {
h = m;
}
}

if (s [l] == n) {
return l;
}
}

return ~0;
}

Anonymous said...

I much prefer the tail recursion implementation, as its simpler to understand, and the compiler will transform it to an iterative version for performance.

bool findNumber(int num, int a[], int start, int end)
{
if (start == end) return a[start] == num;
int mid = ((end - start) / 2) + start;
return findNumber(num, a, start, mid) | findNumber(num, a, mid+1, end);
}

bool findNumber(int num, int a[], int len)
{
return findNumber(num, a, 0, len-1);
}

Anonymous said...

I am not sure where you're getting your info, but good topic. I needs to spend some time learning more or understanding more. Thanks for magnificent info I was looking for this info for my mission.

My homepage; diets that work fast

Anonymous said...

This paragraph provides clear idea for the new viewers of blogging, that truly how to do blogging and site-building.


Feel free to surf to my homepage :: 2013 at 12:01 AM

Anonymous said...

Wow that was odd. I just wrote an really long comment but
after I clicked submit my comment didn't appear. Grrrr... well I'm not
writing all that over again. Regardless, just wanted to say fantastic blog!


Feel free to surf to my web site :: graduate certificate online

Anonymous said...

Gгeat article, exactly ωhat I was looκing for.


Here is my web-ѕite: raspberry ketone uk

Anonymous said...

I гead this artіclе fullу concerning the resemblancе οf moѕt up-to-date and eaгlieг tеchnоlogіes, it's awesome article.

Also visit my site; vitamin shoppe multivitamins one daily

Anonymous said...

Hello to all, the contents existing at this web page are in fact remarkable for people experience,
well, keep up the nice work fellows.

Also visit my web page - healthy waist to height ratio

Anonymous said...

I am regular visitor, how are you everybody? This paragraph
posted at this website is genuinely nice.

My site Buy Raspberry ketone Plus

Anonymous said...

I usually do not drop a leave a response, however I read a great deal of responses
on this page "Write C code to implement the Binary Search algorithm.".
I do have 2 questions for you if it's allright. Could it be only me or does it look like like a few of these remarks appear as if they are written by brain dead folks? :-P And, if you are writing at additional places, I would like to keep up with you. Could you make a list of the complete urls of your social networking pages like your linkedin profile, Facebook page or twitter feed?

My weblog; Nuvo Cleanse

Anonymous said...

It's impressive that you are getting ideas from this paragraph as well as from our dialogue made at this place.

Feel free to surf to my homepage - Beyond Raspberry Ketone Reviews

Anonymous said...

Grеetingѕ! I κnoω thіs is kinda off topіc hoωеveг Ι'd figured I'd ask.
Would you be inteгested in tradіng links or maуbe guest authοгing a blog pοst οr νice-verѕa?
Mу sitе gоes ονer a lot of the same tοpics
as youгs anԁ Ι feеl we cоulԁ greаtly benеfit from each οther.
If уou might be іntereѕtеd feel free tο
send mе an e-maіl. I look foгward
tο hearіng fгοm you!
Tеrгific blog bу the way!



Αlsο viѕit my ωebpagе
- raspberry ketone

Anonymous said...

Hello my family member! I wish to say that this post
is amazing, nice written and include approximately all important infos.
I'd like to see extra posts like this .

My website :: Rvtl Anti Aging Solutions

Anonymous said...

Hello to every single one, it's truly a pleasant for me to pay a visit this web site, it contains important Information.

Also visit my weblog ... Skin care

Anonymous said...

Good day! Would you mind if I share your blog with my facebook
group? There's a lot of people that I think would really appreciate your content. Please let me know. Thanks

Feel free to visit my web page ... Testforce Xtreme

Anonymous said...

Way cool! Some extremely valid points! I appreciate you writing this article
and also the rest of the site is really good.


my site; Buy zinncollection

Anonymous said...

Hello There. I found your blog using msn. This is a very well written article.
I'll make sure to bookmark it and come back to read more
of your useful info. Thanks for the post. I will certainly return.


Here is my site: marvel avengers alliance hack ()

Anonymous said...

Simply want to say your article is as astonishing. The clearness in your post is just nice and i can assume
you're an expert on this subject. Well with your permission let me
to grab your feed to keep up to date with forthcoming post.
Thanks a million and please continue the enjoyable work.|

my web-site; program pit 2013 - nowyprogrampity2013.pl,

Anonymous said...

Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet
my newest twitter updates. I've been looking for a plug-in like this for quite
some time and was hoping maybe you would have some
experience with something like this. Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your
new updates.

Also visit my page: tickets

Anonymous said...

Definitely believe that which you said. Your favorite reason appeared
to be on the web the easiest thing to be aware of.
I say to you, I certainly get irked while people consider
worrikes that they plainly do not know about.

You managed to hit the nail upon the top as
well as defined out the whole thing without having side-effects , people could take a signal.

Will likely be back too get more. Thanks

Have a look at my web-site - treat depression naturally

Anonymous said...

It's going to be finish of mine day, except before ending I am reading this impressive post to
increase my know-how.

Anonymous said...

I am ǥenuinely thankful tо the holder of this wеb page who has shared this wonderful artiсle at heгe.


my web site :: TENS machine

Anonymous said...

Everƴthing is very opеn witɦ ɑ precise explanation օff the issues.
It waѕ truly informative. Your website іs extremely helpful.
Mаny thanks for sharing!

my site; sportsbet

Anonymous said...

To ensure you want an alpha or for beta fundamental key to Heroes of the High?
Surely these kinda on place right now. Before you should happen to jump Youtube or possibly
Craigslist and ebay i affirm accepting an alternative reading the product i’m seeking to advise existing.
Without a Room keys, its a unwind. Any entries you see on craigslist or ebay publicizing beta not to
mention alpha recommendations for Heroes of the storm are
Replica and in addition Ripoffs. A different trailer for Heroes of the Buzz was
used as highlighted during the establishment, which offers heroes from
Blizzard franchises choose StarCraft, Diablo, not to mention World of Warcraft.
Heroes of the Surprise is a future multiplayer online have difficulties topic video
game produced by Blizzard Night-life for Microsof company Home windows.
Flourishing warriors originating from Azeroth,
Paradise, time after time the Koprulu group, and outside of may have been was damaging going
towards the Nexus, a reliable transdimensional environments.
In place you'll plan to check out your Battle.net and thus keep the beta biography website is relevant, understanding that you're signed up towards Heroes of the Bad weather tests.
Just keep in mind this is the sole procedure to gain access presently, thinking that you will be extremely careful of most
email address or just new communication that recommends you may be proven to achieve admittance from some indicates.


My web-site; HEROES OF THE STORM BETA KEY

Anonymous said...

I'm excited to uncover this site. I need to to thank you for ones time just
for this fantastic read!! I definitely liked every bit of it and i also have
you saved to fav to look at new information in your
site.

My weblog; Review of Magic Submitter

Anonymous said...

I've been browsing on-line greater than 3 hours lately, yet
I by no means found any interesting article like yours.
It is pretty price enough for me. Personally, if all web owners
and bloggers made excellent content as you did, the web shall be much more
useful than ever before.

Look at my webpage - algonquian language translations

Anonymous said...

You can take comfort in knowing that a personal injury attorney Mesa or a car accident lawyer Mesa will be on their
side. Another accident is just waiting to happen if you just brush it off and take an apology
off your boss. This is the reason you may want to consider appointing a work injury lawyer.


my blog ... plaintiff personal injury toronto

Anonymous said...

Your employees will likely be very unhappy to received
payment delayed. Outsourcing particular business tasks can enable you to definitely get back resources and energy to
focus in your core competencies. All payroll companies generally offer similar forms
of core services: calculating payroll and tax obligations for each and every employee, providing management reports,
and printing and delivering checks.

Anonymous said...

Hey excellent website! Does running a blog like this require a
great deal of work? I have virtually no expertise in programming
however I had been hoping to start my own blog soon. Anyways, should you have any ideas or tips for new
blog owners please share. I understand this is off subject however I simply
had to ask. Kudos!

my web blog; queens condo inspection (www.youtube.com)

Anonymous said...

I visited various blogs but the audio feature for audio songs current at
this web page is truly superb.

Feel free to visit my blog: plumbing Scottsdale

Anonymous said...

Hi my family member! I wish to say that this post is amazing,
great written and come with approximately all important infos.
I would like to peer extra posts like this .

Review my page :: cna classes online texas (odiscmim.blog.com)

Anonymous said...

Listed here are the benefits that you can enjoy using the
newest trends within the payroll. Since long all happen to be utilizing bookkeeping programming
and it is essential to understand just what the contrast between ERP and bookkeeping programming is.

s government is caught again within an ICT policy scandal that caused
millions of dollars in taxpayer.

Feel free to visit my site; payroll service providers

Anonymous said...

Hey very nice blog!

my website prograce reviews

Anonymous said...

So in case you be a victim of id theft, the one thing to recollect is just not permit it become an ongoing set of things to complete.
Do you will find it challenging to manage your bank card
debt. And, even when you are doing get approved to get a loan or even a new bank card,
you'll usually have higher interest levels about the loan than what's provided to people with good credit
profile.

Here is my homepage ... credit Reporting Companies

Anonymous said...

This piece oof writing is truly a good one it assists new net people, wwho are wishing in favor of blogging.



my homepage - World news

Anonymous said...

If you are going for most excellent contents like
I do, only visit this web site daily as it gives feature contents, thanks

My weblog; family law ,,scottsdale

Anonymous said...

Toshiba took several special steps to relieve environment pollution inside manufacturing of the TV set models.
The Buyer's Guide is an element of the sales contract and overrides any conflicting provisions inside contract.

Remember which you first need to explore your home
warranty update and find out what exactly is missing.


Also visit my weblog: best home warranty plans

Anonymous said...

I've read several good stuff here. Certainly worth bookmarking for revisiting.
I wonder how much effort you set to create this sort of great
informative web site.

My webpage: terraria download

Anonymous said...

Hi colleagues, pleasant piece of writing and good urging commehted here, I am actually enjoying
by these.

Feel freee to surf to mmy homepage - clash of clans guides

Anonymous said...

Pretty component to content. I simply stumbled upon your site and in accession capital to claim that
I get actually loved account your blog posts. Any way I'll be subscribing on your augment or
even I success you access persistently rapidly.

Feel free to visit my page; Ice Age Village Hack

Anonymous said...

It's an amazing article foor аll tɦe internet visitors; theƴ wipl take benefit
from it I aam sսre.

Review my webpage phen375, ,

Unknown said...

If you desire to get a benefit from this post then you need to apply these strategies to your own internet site.


Please review my video: Seattle WA Tax Attorney
Tax Attorney Seattle WA

Anonymous said...

My developer is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he's tryiong none the less. I've been using WordPress on several websites for about a year and
am concerned about switching to another
platform. I have heard fantastic things about blogengine.net.
Is there a way I can transfer all my wordpress content into it?
Any kind of help would be greatly appreciated!


Check out my web blog buy used car parts chicago

Anonymous said...

External Auditor Wimbley from Sardis, spends time with pursuits like reading to the, nike free and string figures.
Gains immense encouragement from life by touring places for example Historic Centre of Saint Petersburg and Related Groups of Monuments.


Here is my website :: nike air max 1

Anonymous said...

Everyone loves it when people come together and share thoughts. Great blog, keep it up! Hope you love my site สล็อ