Thread: studying for exam, have a question!

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    53

    studying for exam, have a question!

    Im looking over the practice exam our professor put up, and Im having a hard time understanding one of the problems. It goes like this:

    Given the following array of character strings,
    Code:
    char *list[7]={ "Alpha",
                            "Bravo",
                            "Charlie",
                            "Echo",
                             "Foxtrot",
                             "Golf",
                             "Hotel"};
    In a binary search (where the list is sorted), how many comparisons would be required to determine that the string "Delta" is not in the list? List the strings that would be compared to "Delta" in a standard binary search in the order that the comparisons would be made.

    The answer he gives is this:

    1.) Echo (element 3)
    2.) Bravo (element 1)
    3.) Charlie (element 2)

    Im having a hard time understanding how he came up with that, can anyone explain it to me?

  2. #2
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    What, according to you should be the answer? Do you know anything about binary search? What have you understood in this question?
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    53
    Quote Originally Posted by BEN10 View Post
    What, according to you should be the answer? Do you know anything about binary search? What have you understood in this question?
    I thought it would go in alphabetical order, so my answer would have been alpha, brave, charlie, then echo.

  4. #4
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    It's not a linear search, it's a binary search where the mid element is taken and searched with "delta", so the list is continuosly divided into two halves. Keep in mind it's not a linear search. For more theory use google for "binary search".
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  5. #5
    Registered User
    Join Date
    Jun 2009
    Posts
    53
    Alpha Bravo Charlie |Echo| Foxtrot Golf Hotel
    Alpha |Bravo| Charlie
    Alpha |Charlie|

    why Charlie and not Alpha at the end? or could either one have worked?

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> why Charlie and not Alpha at the end? or could either one have worked?

    Well, since Bravo < Delta, we know that anything before that will also be less.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  7. #7
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Work according to this algorithm:
    if(low<high)
    return -1;
    mid=(low+high)/2;
    if(x==a[mid])
    return mid;
    if(x<a[mid])
    search for x in a[low] to a[mid-1];
    else
    search for x in a[mid+1] to a[high].
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  8. #8
    Registered User
    Join Date
    Jun 2009
    Posts
    53
    Quote Originally Posted by BEN10 View Post
    Work according to this algorithm:
    if(low<high)
    return -1;
    mid=(low+high)/2;
    if(x==a[mid])
    return mid;
    if(x<a[mid])
    search for x in a[low] to a[mid-1];
    else
    search for x in a[mid+1] to a[high].
    thank you sir, youve been very helpful

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Never played "guess a number I'm thinking of between 1 and 10", before?

    You cut the difference between 1 and 10, in half, with every guess:

    I guess:

    5 (secret number is 9) 10/2 = 5

    "You're too low"

    (Lower limit is now 6, so 10-6= 4 and 4/2 = 2. 6 + 2 = 8

    8

    "Still too low"
    (9 is the new lower limit, 10-9= 1 and 1/2 = 0 with integer division. 9 + 0 = 9)

    9

    You guessed it.

    The upper limit stayed at 10 in this example, but it moves downward, just like the lower limit or floor, moves upward, in the Binary Search.

    It seems quite trivial, but with a lot of numbers, it does a fantastic job. It also is the basis for a heuristic we use to solve a lot of programming problems:

    Take a big problem, and chop it up successively into smaller one's, and solve them. Finally, you have the whole problem solved. Quicksort is a fine example of this.

  10. #10
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> It seems quite trivial, but with a lot of numbers, it does a fantastic job.

    Yep. If you're good with juggling numbers in your head it makes a great party trick: "Pick a number between 1 and 1,000,000 and I'll guess the number within 20 tries!".
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  11. #11
    Registered User
    Join Date
    Jun 2009
    Posts
    53
    Thanks for detailed help guys

    Quote Originally Posted by Sebastiani View Post
    >> It seems quite trivial, but with a lot of numbers, it does a fantastic job.

    Yep. If you're good with juggling numbers in your head it makes a great party trick: "Pick a number between 1 and 1,000,000 and I'll guess the number within 20 tries!".
    Crap. there was a true false question about binary searches on the exam that said something along the lines of "on average the number of attempts the algorithm makes are usually half the number of elements in the list". I put true

  12. #12
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    The correct answer is: for a binary search, worst case is log2(N) attempts. If you're lucky it could match earlier than that.

    Linear searches average half the number of elements.

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    When you try to find a name in a phone book (archaic concept, I know), do you start at page 1 and start reading down the list until you reach the name?

    Or do you use a slightly more intelligent strategy?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    Quote Originally Posted by wankel View Post
    Crap. there was a true false question about binary searches on the exam that said something along the lines of "on average the number of attempts the algorithm makes are usually half the number of elements in the list". I put true
    That is a simple mistake. Half would be a linear search. It may help to look at the complexities of the algorithms
    Code:
    linear  = O(n) // data spread randomly
    binary = O(log(n)) // data in order
    Now on a linear search, assuming the probably of an element being the one you want is 1/n where n is the size of the list to be search. On average you will find the element by the middle. So you have n/2 searches or half of the list (which is what you said binary search was)

    Binary search is a different story. O(log(n)) is much better because a log base 2 of n halves the search space every time. So to search you have to go through log(n) elements in the list.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  2. Studying for Final, Couple Questions...
    By stewade in forum C Programming
    Replies: 4
    Last Post: 05-10-2004, 05:02 PM
  3. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  4. Question about linked lists.
    By cheeisme123 in forum C++ Programming
    Replies: 6
    Last Post: 02-25-2003, 01:36 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 01:47 AM