Wanted to check if I was doing this correctly.
Binary Search: Find number of comparisons needed
5 11 18 40 45 58 62 75 88 95 100
A. 45 --> 3 needed
B. 96 --> 3 needed
Welcome to the Java Programming Forums
The professional, friendly Java community. 21,500 members and growing!
The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.
>> REGISTER NOW TO START POSTING
Members have full access to the forums. Advertisements are removed for registered users.
LinkBack URL
About LinkBacks
Sorting/Search
Wanted to check if I was doing this correctly.
Binary Search: Find number of comparisons needed
5 11 18 40 45 58 62 75 88 95 100
A. 45 --> 3 needed
B. 96 --> 3 needed
Last edited by dx8292; February 13th, 2012 at 08:30 PM. Reason: caught a mistake with selection sort
Re: Sorting/Search
Well, wikipedia explains all the algorithms relatively well, which should clear up any confusion
Selection sort - Wikipedia, the free encyclopedia
Binary search algorithm - Wikipedia, the free encyclopedia
Insertion sort - Wikipedia, the free encyclopedia
KevinWorkman (February 13th, 2012)
Re: Sorting/Search
The thing Binary Search I wasn't really sure was when it checks the middle number and if it's not value that was being searched for, does it start searching in reverse order if the first half needs to be checked or does it start from the beginning?
Re: Sorting/Search
You can find a word in a dictionary (a book with pages made of wood pulp) by opening it in the middle. If the word is not on the two pages you can see, split the half that should contain the word in half and look again. Repeat until you find the word. You know which half to split in half because you the dictionary's entries are sorted. Barring bad splits (not half-half but 60-40, for example), you should expect to find every word you think of within log_2 the number of pages in the dictionary. Try it out for yourself.
You answers of '6' for a binary search of 11 items are certainly too high - it should never take (a program) more than 4 (log_2(11)) attempts.
Re: Sorting/Search
What do mean? I want to see how many comparisons it would take to find 45. The first comparison would be to 45 and the midpoint number (58)
Then the rest of the comparisons would be to each element in the first half of the list. I just don't which way it would check.
45 to 5; 45 to 11; 45 to 18; 45 to 40; 45 to 45
OR
45 to 45 and its end since the value has been found, so you wouldn't have to do 45 to 40; 45 to 18; 45 to 11; 45 to 5
Am I doing it incorrectly?
Are you saying that ln(# of items in list)/ln2 gets me the number of comparisons everytime?
Last edited by dx8292; February 13th, 2012 at 05:11 PM.
Re: Sorting/Search
5 11 18 40 45 58 62 75 88 95 100 search 45 at middle element (index 11/2 = 5) 58 - noOriginally Posted by dx8292
45 is less than 58 so middle element of less-than half (index 5/2 = 2) is 18 - no
45 is greater than 18 so middle element of greater-than half (index (2 + (5-2) / 2 = 3) is 40 - no
45 is greater than 40 so middle element of greater-than half (index (3 + (5-3) / 2 = 4) is 45.
Found in 4.
dx8292 (February 13th, 2012)
Re: Sorting/Search
(1+11)/2=6
(1+5)/2=3
(4+5)/2=4.5 round to 5
I got three.
Re: Sorting/Search
Well, if you programmed in a language that worked that way, you might well get that result. The contributors on here who invite us all to read articles about computer science and the Java API and Language Specification are not doing it out of spite - there are things in those documents which you need to know so that you can be a more effective programmer.
Types, Values, and Variables
The language uses round toward zero when converting a floating value to an integer (§5.1.3), which acts, in this case, as though the number were truncated, discarding the mantissa bits. Rounding toward zero chooses at its result the format's value closest to and no greater in magnitude than the infinitely precise result.
Reply With Quote
