# Sorting/Search

• February 11th, 2012, 06:14 PM
dx8292
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
• February 13th, 2012, 01:04 PM
Tjstretch
Re: Sorting/Search
• February 13th, 2012, 01:45 PM
dx8292
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?
• February 13th, 2012, 03:02 PM
Sean4u
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.
• February 13th, 2012, 03:42 PM
dx8292
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?
• February 13th, 2012, 04:27 PM
Sean4u
Re: Sorting/Search
Quote:

Originally Posted by dx8292
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.

5 11 18 40 45 58 62 75 88 95 100 search 45 at middle element (index 11/2 = 5) 58 - no
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.
• February 13th, 2012, 07:29 PM
dx8292
Re: Sorting/Search
(1+11)/2=6
(1+5)/2=3
(4+5)/2=4.5 round to 5

I got three.
• February 14th, 2012, 03:09 AM
Sean4u
Re: Sorting/Search
Quote:

Originally Posted by dx8292
(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.

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.