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
Printable View
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
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
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?
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.
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?
5 11 18 40 45 58 62 75 88 95 100 search 45 at middle element (index 11/2 = 5) 58 - noQuote:
Originally 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.
(1+11)/2=6
(1+5)/2=3
(4+5)/2=4.5 round to 5
I got three.
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.Quote:
Originally Posted by dx8292
Types, Values, and Variables
Quote:
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.