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.

Results 1 to 8 of 8

Thread: Sorting/Search

  1. #1
    Junior Member
    Join Date
    Jan 2012
    Posts
    21
    My Mood
    Confused
    Thanks
    5
    Thanked 1 Time in 1 Post

    Default 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 07:30 PM. Reason: caught a mistake with selection sort

  2. #2
    Forum VIP
    Join Date
    Oct 2010
    Posts
    275
    My Mood
    Cool
    Thanks
    32
    Thanked 54 Times in 47 Posts
    Blog Entries
    2

    Default Re: Sorting/Search


  3. The Following User Says Thank You to Tjstretch For This Useful Post:

    KevinWorkman (February 13th, 2012)

  4. #3
    Junior Member
    Join Date
    Jan 2012
    Posts
    21
    My Mood
    Confused
    Thanks
    5
    Thanked 1 Time in 1 Post

    Default 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?

  5. #4
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default 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.

  6. #5
    Junior Member
    Join Date
    Jan 2012
    Posts
    21
    My Mood
    Confused
    Thanks
    5
    Thanked 1 Time in 1 Post

    Default 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 04:11 PM.

  7. #6
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Sorting/Search

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

  8. The Following User Says Thank You to Sean4u For This Useful Post:

    dx8292 (February 13th, 2012)

  9. #7
    Junior Member
    Join Date
    Jan 2012
    Posts
    21
    My Mood
    Confused
    Thanks
    5
    Thanked 1 Time in 1 Post

    Default Re: Sorting/Search

    (1+11)/2=6
    (1+5)/2=3
    (4+5)/2=4.5 round to 5

    I got three.

  10. #8
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Sorting/Search

    Quote Originally Posted by dx8292 View Post
    (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

    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.

Similar Threads

  1. Graph Search Theory with extend of BFS, UFS and A* Search in grid
    By keat84 in forum Java Theory & Questions
    Replies: 1
    Last Post: February 7th, 2012, 08:46 AM
  2. [ask] about sorting number.
    By bontet in forum What's Wrong With My Code?
    Replies: 1
    Last Post: October 30th, 2010, 02:07 PM
  3. Sorting/Lexicographic =)
    By jcs990 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: March 12th, 2010, 10:19 PM
  4. [SOLVED] sorting
    By kite98765 in forum Algorithms & Recursion
    Replies: 8
    Last Post: February 4th, 2010, 07:34 AM
  5. Sorting Algorithms
    By Dalisra in forum Java Code Snippets and Tutorials
    Replies: 1
    Last Post: November 10th, 2009, 08:24 PM