Hello All:
This is my first post, so hello everyone. I am having a little
difficulty understanding how binary searching works. I am currently in
an introductory computer science course. I understand the major
halving concept. But the examples in my book only deal with an odd
amount of items. So, when we have an even number of items what does
the middle equal? If you do the (beginning + end)/2 with an even
number of items you get a decimal. I have looked on line and found
that the programs using binary search set the middle as
floor((beginning + end)/2). So do you always round down?
Below I have done an example. Am I doing it right? Do I have the
concepts down?
For example: if we had the list of names: Ann Cleo Cathy Fred Katie
Melony Steve Ted
and we wanted to search for Ted: I would first find the middle
((1+8)/2)=4.5=4 which is Fred. Since Ted follows Fred I would set
beginning to 5 and end to 8. I would then find the middle of 5 and 8
((5+8)/2)=6.5=6 which equals Melony. Since Ted follows Melony I would
set beginning to 7 and end to 8. I would then find the middle of 7 and
8 ((7+8)/2)=7.5=7 which equals Steve. Since Ted follows Steve I would
set beginning to 8 and end to 8 making the middle 8 which equals
Ted.
If I wanted to search for Cleo: I would first find the middle
((1+8)/2)=4.5=4 which is Fred. Since Cleo precedes Fred I would set
beginning to 1 and end to 3. The middle would be ((3+1)/2)=2 which
equals Cleo. And thats it.
If I wanted to search for Joe:I would first find the middle
((1+8)/2)=4.5=4 which is Fred. Since Joe precedes Fred I would set
beginning to 1 and end to 3. The middle would be 2 which equals Cleo.
Since Joe follows Cleo I would set beginning to 3 and end to 3 which
makes the middle 3 which equals Cathy. Since Joe follows Cathy I would
set beginning to 4 and end to 3. Thus the loop doesn't repeat and we
now know that Joe isn't in the list.
Did I get the steps in these examples correct? Do I have the concept?
Thank you. And again, I am happy to be apart of this group.
Stephen
