beginner help with sequential and binary search

Discussion in 'Java' started by Ray Leon, Jul 10, 2008.

  1. Ray Leon

    Ray Leon Guest

    Dear Sirs or Madam:

    I have completed a quiz and just want feedback on any possible mistake I
    have made if any. Any help is greatly appreciated. I think I have the
    correct answers for the following questions:

    1. Let myArray represents an array of 5 elements with the following values
    in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
    the element 30 (the third element) using:



    a. Sequential search (10 points)

    b. Binary search (10 points)



    Answer below:



    Sequential search - Three (3)

    Binary search - One (1)









    2. Consider the array consisting of 7 elements sorted in ascending order.
    What is the Maximum number of comparisons that need to be done to find any
    given element using:



    a. Sequential search (10 points)

    b. Binary search (10 points)



    Answer below:



    Sequential search - Seven (7)

    Binary search - Two (2)



    Thanks



    Ray
     
    Ray Leon, Jul 10, 2008
    #1
    1. Advertising

  2. Ray Leon

    Willem Guest

    Ray Leon wrote:
    ) Dear Sirs or Madam:
    )
    ) I have completed a quiz and just want feedback on any possible mistake I
    ) have made if any. Any help is greatly appreciated. I think I have the
    ) correct answers for the following questions:

    It would be helpful if you would give not only the answers,
    but also the reasoning that you used to get this answer.

    By the way: You got one of the last two answers wrong.
    Which one is the wrong one depends on a detail that was
    not given in the question.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Jul 10, 2008
    #2
    1. Advertising

  3. Ray Leon

    Gene Guest

    On Jul 10, 2:35 pm, "Ray Leon" <> wrote:
    > Dear Sirs or Madam:
    >
    > I have completed a quiz and just want feedback on any possible mistake I
    > have made if any. Any help is greatly appreciated. I think I have the
    > correct answers for the following questions:
    >
    > 1. Let myArray represents an array of 5 elements with the following values
    > in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
    > the element 30 (the third element) using:
    >
    > a. Sequential search (10 points)
    >
    > b. Binary search (10 points)
    >
    > Answer below:
    >
    > Sequential search - Three (3)
    >
    > Binary search - One (1)
    >
    > 2. Consider the array consisting of 7 elements sorted in ascending order.
    > What is the Maximum number of comparisons that need to be done to find any
    > given element using:
    >
    > a. Sequential search (10 points)
    >
    > b. Binary search (10 points)
    >
    > Answer below:
    >
    > Sequential search - Seven (7)
    >
    > Binary search -  Two (2)
    >


    It's fairly likely you've given close the desired answers. But the
    devil is in the details.

    1) Are your algorithms required to reject searches for items that
    aren't there? If so, then, for example, the last answer is (at least)
    3. If not, then the second last answer is 6 (i.e. if you've checked 6
    items and it has to be in the list, then it must be the 7th.

    2) What is a "comparison?" Most programming languages don't provide 3-
    way branches for <, =, >, so each pass through the binary search loop
    actually requires _two_ comparisons: one for strict equality and one
    for inequality. It's the same if you decide to implement linear
    search that "quits early" because the array is sorted.

    3) Again if the search item might not be found, then the
    implementation of linear search becomes a bit tricky because you might
    run off then end of the list. You can solve this efficiently - with
    just one extra comparison - by adding a "sentinel" item at the end
    that's equal to the key. Or you can use a separate counter, but that
    adds one comparison _per iteration_ of the search loop.
     
    Gene, Jul 10, 2008
    #3
  4. Ray Leon wrote:
    > I have completed a quiz and just want feedback on any possible mistake I
    > have made if any. Any help is greatly appreciated. I think I have the
    > correct answers for the following questions:
    >
    > 1. Let myArray represents an array of 5 elements with the following values
    > in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
    > the element 30 (the third element) using:
    >
    > a. Sequential search (10 points)
    >
    > b. Binary search (10 points)
    >
    > Answer below:
    >
    > Sequential search - Three (3)
    >
    > Binary search - One (1)


    The answer may not be that simple because "binary search" is not a
    completely unambiguous term. More precisely, you have to state what
    happens if the binary search is performed on an array which may contain
    repeated values: Should the binary search just tell whether the element
    exists in the array, or if there's more than one such element, should it
    return a handle to the first one in the array?

    If "binary search" means "tell me if this element exists in the
    array", then the answer of 1 is correct. However, if it means "give me a
    handle to the first appearance of this element in the array", then the
    correct answer becomes 3 (because the binary search needs to be
    continued even if an element with the same value is found immediately).

    > 2. Consider the array consisting of 7 elements sorted in ascending order.
    > What is the Maximum number of comparisons that need to be done to find any
    > given element using:
    >
    > a. Sequential search (10 points)
    >
    > b. Binary search (10 points)
    >
    > Answer below:
    >
    > Sequential search - Seven (7)
    >
    > Binary search - Two (2)


    Even if we are only checking for the existence of the element in the
    array, the binary search would require in the worst case 4 comparisons:
    the first comparison checks the fourth element, then, assuming that
    element is too small, it checks the fifth element (because the middle of
    4 and 7 is 5.5, which gets rounded eg. to 5), then assuming that one is
    also too small, it checks the sixth element (which is the middle of 5
    and 7), and if that also was too small, finally the seventh.
     
    Juha Nieminen, Jul 10, 2008
    #4
  5. Ray Leon

    Gene Guest

    On Jul 10, 4:56 pm, Juha Nieminen <> wrote:
    > Ray Leon wrote:
    > > I have completed a quiz and just want feedback on any possible mistake I
    > > have made if any. Any help is greatly appreciated. I think I have the
    > > correct answers for the following questions:

    >
    > > 1. Let myArray represents an array of 5 elements with the following values
    > > in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
    > > the element 30 (the third element) using:

    >
    > > a. Sequential search (10 points)

    >
    > > b. Binary search (10 points)

    >
    > > Answer below:

    >
    > > Sequential search - Three (3)

    >
    > > Binary search - One (1)

    >
    >   The answer may not be that simple because "binary search" is not a
    > completely unambiguous term. More precisely, you have to state what
    > happens if the binary search is performed on an array which may contain
    > repeated values: Should the binary search just tell whether the element
    > exists in the array, or if there's more than one such element, should it
    > return a handle to the first one in the array?
    >
    >   If "binary search" means "tell me if this element exists in the
    > array", then the answer of 1 is correct. However, if it means "give me a
    > handle to the first appearance of this element in the array", then the
    > correct answer becomes 3 (because the binary search needs to be
    > continued even if an element with the same value is found immediately).
    >
    > > 2. Consider the array consisting of 7 elements sorted in ascending order.
    > > What is the Maximum number of comparisons that need to be done to find any
    > > given element using:

    >
    > > a. Sequential search (10 points)

    >
    > > b. Binary search (10 points)

    >
    > > Answer below:

    >
    > > Sequential search - Seven (7)

    >
    > > Binary search -  Two (2)

    >
    >   Even if we are only checking for the existence of the element in the
    > array, the binary search would require in the worst case 4 comparisons:
    > the first comparison checks the fourth element, then, assuming that
    > element is too small, it checks the fifth element (because the middle of
    > 4 and 7 is 5.5, which gets rounded eg. to 5), then assuming that one is
    > also too small, it checks the sixth element (which is the middle of 5
    > and 7), and if that also was too small, finally the seventh.- Hide quoted text -
    >
    > - Show quoted text -


    I can't get 4. The first comparison looks at the 4th element. Either
    it's successful or it rejects 4 elements, leaving 3. The second
    comparison looks at the middle of the 3. Either it's successful or it
    rejects 2 elements, which leaves 1. The question is whether a 3rd
    comparison is needed to check for a match because the searched-for
    element might be missing altogether. So it's either 2 or 3.
     
    Gene, Jul 11, 2008
    #5
  6. Ray Leon

    popeyerayaz Guest

    On Jul 10, 6:38 pm, pete <> wrote:
    > Juha Nieminen wrote:
    > > Ray Leon wrote:
    > >> I have completed a quiz and just want feedback on any possible mistake I
    > >> have made if any. Any help is greatly appreciated. I think I have the
    > >> correct answers for the following questions:

    >
    > >> 1. Let myArray represents an array of 5 elements with the following values
    > >> in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
    > >> the element 30 (the third element) using:

    >
    > >> a. Sequential search (10 points)

    >
    > >> b. Binary search (10 points)

    >
    > >> Answer below:

    >
    > >> Sequential search - Three (3)

    >
    > >> Binary search - One (1)

    >
    > >   The answer may not be that simple because "binary search" is not a
    > > completely unambiguous term. More precisely, you have to state what
    > > happens if the binary search is performed on an array which may contain
    > > repeated values: Should the binary search just tell whether the element
    > > exists in the array, or if there's more than one such element, should it
    > > return a handle to the first one in the array?

    >
    > >   If "binary search" means "tell me if this element exists in the
    > > array", then the answer of 1 is correct. However, if it means "give me a
    > > handle to the first appearance of this element in the array", then the
    > > correct answer becomes 3 (because the binary search needs to be
    > > continued even if an element with the same value is found immediately).

    >
    > >> 2. Consider the array consisting of 7 elements sorted in ascending order.
    > >> What is the Maximum number of comparisons that need to be done to find any
    > >> given element using:

    >
    > >> a. Sequential search (10 points)

    >
    > >> b. Binary search (10 points)

    >
    > >> Answer below:

    >
    > >> Sequential search - Seven (7)

    >
    > >> Binary search -  Two (2)

    >
    > >   Even if we are only checking for the existence of the element in the
    > > array, the binary search would require in the worst case 4 comparisons:
    > > the first comparison checks the fourth element, then, assuming that
    > > element is too small, it checks the fifth element (because the middle of
    > > 4 and 7 is 5.5, which gets rounded eg. to 5), then assuming that one is
    > > also too small, it checks the sixth element (which is the middle of 5
    > > and 7), and if that also was too small, finally the seventh.

    >
    > That is wrong.
    > If it were element 7,
    > the binary search pattern would be 4,6,7.
    >
    > Incrementing from 4 to 7,
    > just obviously isn't binary search.
    >
    > /* BEGIN new.c output */
    >
    > int array[] = {1,2,3,4,5,6,7};
    >
    > Searching for value 1 in array.
    > Value 1, found in array[0].
    > 3 comparisons were made.
    >
    > Searching for value 2 in array.
    > Value 2, found in array[1].
    > 2 comparisons were made.
    >
    > Searching for value 3 in array.
    > Value 3, found in array[2].
    > 3 comparisons were made.
    >
    > Searching for value 4 in array.
    > Value 4, found in array[3].
    > 1 comparisons were made.
    >
    > Searching for value 5 in array.
    > Value 5, found in array[4].
    > 3 comparisons were made.
    >
    > Searching for value 6 in array.
    > Value 6, found in array[5].
    > 2 comparisons were made.
    >
    > Searching for value 7 in array.
    > Value 7, found in array[6].
    > 3 comparisons were made.
    >
    > /* END new.c output */
    >
    > /* BEGIN new.c */
    >
    > #include <stdio.h>
    >
    > #define NMEMB(A)        (sizeof(A) / sizeof *(A))
    >
    > int Comps;
    >
    > void *b_search(const void *key, const void *base,
    >                 size_t nmemb, size_t size,
    >                 int (*compar)(const void *, const void *));
    > int comparison(const void *arg1, const void *arg2);
    >
    > int main(void)
    > {
    >      int array[] = {1,2,3,4,5,6,7};
    >      const int target[] = {1,2,3,4,5,6,7};
    >      unsigned index;
    >      int *found;
    >
    >      puts("/* BEGIN new.c output */\n");
    >      puts("int array[] = {1,2,3,4,5,6,7};\n");
    >      for (index = 0; index != NMEMB(target); ++index) {
    >          Comps = 0;
    >          printf("Searching for value %d in array.\n", target[index]);
    >          found = b_search(target + index, array, NMEMB(array)
    >              , sizeof*array, comparison);
    >          if (found != NULL) {
    >              printf("Value %d, found in array[%u].\n"
    >                  "%d comparisons were made.\n"
    >                  , target[index]
    >                  , found - array, Comps);
    >          } else {
    >              printf("Value %d, not found in array.\n"
    >                  "%d comparisons were made.\n"
    >                  , target[index], Comps);
    >          }
    >          putchar('\n');
    >      }
    >      puts("/* END new.c output */");
    >      return 0;
    >
    > }
    >
    > void *b_search(const void *key, const void *base,
    >                 size_t nmemb, size_t size,
    >                 int (*compar)(const void *, const void *))
    > {
    >      int comp;
    >      size_t middle, high, low;
    >      const unsigned char *array, *found;
    >
    >      found = NULL;
    >      if (nmemb != 0) {
    >          array = base;
    >          low = 0;
    >          high = nmemb;
    >          do {
    >              nmemb = high - low;
    >              middle = nmemb / 2 + low;
    >              base = middle * size + array;
    >              comp = compar(key, base);
    >              if (comp > 0) {
    >                  low = middle;
    >              } else {
    >                  high = middle;
    >                  if (comp == 0) {
    >                      found = base;
    >                      break;
    >                  }
    >              }
    >          } while (nmemb != 1);
    >      }
    >      return (void *)found;
    >
    > }
    >
    > int comparison(const void *arg1, const void *arg2)
    > {
    >      ++Comps;
    >      return *(const int *)arg2  > *(const int *)arg1 ? -1
    >           : *(const int *)arg2 != *(const int *)arg1;
    >
    > }
    >
    > /* END new.c */
    >
    > --
    > pete


    2. Consider the array consisting of 7 elements sorted in ascending
    order. What is the Maximum number of comparisons that need to be done
    to find any given element using:

    a. Sequential search (10 points)
    b. Binary search (10 points)

    Answer below:

    a. Since the total number of elements is seven, and the value is
    unknown I can only assume that the maximum number of comparisons may
    be the total amount of elements, seven (7).

    b. The binary search for any given number is what I can’t figure out.
    I have attempted to use the following code and formula but am very
    confused as to what the answer could be. I can get certain values but
    when I try for example the number two as the value to search for it
    just doesn’t work.


    low = 0
    high = N
    while (low < high) {
    mid = (low + high)/2;
    if (A[mid] < value)
    low = mid + 1;
    else
    //can't be high = mid-1: here A[mid] >= value,
    //so high can't be < mid if A[mid] == value
    high = mid;
    }

    if (low < N) and (A[low] == value)
    return low
    else
    return not_found

    any help greatly appreciated.
     
    popeyerayaz, Jul 11, 2008
    #6
  7. popeyerayaz <> writes:

    <snip all of pete's post -- you don't seem to be replying to it>

    > 2. Consider the array consisting of 7 elements sorted in ascending
    > order. What is the Maximum number of comparisons that need to be done
    > to find any given element using:
    >
    > a. Sequential search (10 points)
    > b. Binary search (10 points)
    >
    > Answer below:
    >
    > a. Since the total number of elements is seven, and the value is
    > unknown I can only assume that the maximum number of comparisons may
    > be the total amount of elements, seven (7).


    Depending on the exact meaning of the question, this is probably
    wrong. If comparisons means "element comparisons" (i.e. any tests
    required to run the loop are excluded) then you can find an element
    that _you know is there_ with N-1 tests in sequence:

    for i in 1..N-1 do
    if element = value
    return i
    return N

    but the error is probably in the wording of the question. This is a
    case where writing lots might help you out.

    > b. The binary search for any given number is what I can’t figure out.
    > I have attempted to use the following code and formula but am very
    > confused as to what the answer could be. I can get certain values but
    > when I try for example the number two as the value to search for it
    > just doesn’t work.
    >
    > low = 0
    > high = N
    > while (low < high) {
    > mid = (low + high)/2;
    > if (A[mid] < value)
    > low = mid + 1;
    > else
    > //can't be high = mid-1: here A[mid] >= value,
    > //so high can't be < mid if A[mid] == value
    > high = mid;
    > }
    >
    > if (low < N) and (A[low] == value)
    > return low
    > else
    > return not_found
    >
    > any help greatly appreciated.


    It looks fine to me. Maybe what you are running is not quite the same
    code (or maybe I've missed a bug in it, but I tested it *and* reasoned
    about it!).

    --
    Ben.
     
    Ben Bacarisse, Jul 11, 2008
    #7
  8. Gene wrote:
    > I can't get 4. The first comparison looks at the 4th element. Either
    > it's successful or it rejects 4 elements, leaving 3.


    You can't do that with one single comparison. In order to do that you
    would have to first look if the 4th element is equal to the searched
    element, and if it isn't, then you have to look if it's smaller (in
    order to decide which half you discard), after which you can continue
    with the correct half without the 4th element included.
    That would make two comparisons per step. The total number of
    comparisons in the worst case would grow to at least 5 (depending on how
    you implement the check for a range of one single element).

    In order to have only one comparison per step, you have to look if the
    4th element is smaller than the searched element, and then choose the
    correct half *including* that 4th element. (You can't discard it because
    it might actually be the searched element.)
    That is, the first step discards 3 elements and continues with the
    remaining 4.
    This way the total number of comparisons in the worst case is 4.
     
    Juha Nieminen, Jul 11, 2008
    #8
  9. pete wrote:
    > if (comp > 0) {
    > low = middle;
    > } else {
    > high = middle;
    > if (comp == 0) {


    You are making *two* comparisons per step here, thus doubling the
    total number of comparisons.
     
    Juha Nieminen, Jul 11, 2008
    #9
  10. Lew <> writes:

    > popeyerayaz <> writes:
    >>> low = 0
    >>> high = N
    >>> while (low < high) {
    >>> mid = (low + high)/2;
    >>> if (A[mid] < value)
    >>> low = mid + 1;
    >>> else
    >>> //can't be high = mid-1: here A[mid] >= value,
    >>> //so high can't be < mid if A[mid] == value
    >>> high = mid;
    >>> }
    >>>
    >>> if (low < N) and (A[low] == value)
    >>> return low
    >>> else
    >>> return not_found
    >>>
    >>> any help greatly appreciated.

    >
    > Weird to see C code in a message thread that was apparently geared to
    > the Java community.


    Actually it is not C either. I assumed it was pseudo-code (though it
    is not a million miles from either, style issues aside).

    > Ben Bacarisse wrote:
    >> It looks fine to me. Maybe what you are running is not quite the same
    >> code (or maybe I've missed a bug in it, but I tested it *and* reasoned
    >> about it!).

    >
    > As long as both low and high stay below Integer.MAX_VALUE/2, or to put
    > it another way, as long as the value position is below
    > Integer.MAX_VALUE/2.


    Not if you do, as I did, and turn the pseudo-code into C with low and
    high unsigned (size_t is a good choice). Then you get no overflow
    issues. A good values for "not_found" is then N.

    I don't know if Java has a non-overflowing integer type.

    --
    Ben.
     
    Ben Bacarisse, Jul 11, 2008
    #10
  11. Ray Leon

    Guest

    Lew writes:
    > > As long as both low and high stay below Integer.MAX_VALUE/2, or to put
    > > it another way, as long as the value position is below
    > > Integer.MAX_VALUE/2.


    Ben Bacarisse wrote:
    > Not if you do, as I did, and turn the pseudo-code into C with low and
    > high unsigned (size_t is a good choice).  Then you get no overflow
    > issues.  A good values for "not_found" is then N.


    Given the OP's original distribution to a Java newsgroup and not a C
    newsgroup, I looked at the problem strictly from a Java perspective/

    > I don't know if Java has a non-overflowing integer type.


    It does not, by design.

    But surely size_t does overflow in C? Unsignedness doesn't prevent
    overflow, it just shifts the trouble point.

    --
    Lew
     
    , Jul 11, 2008
    #11
  12. Dann Corbit wrote:
    > "Juha Nieminen" <> wrote in message
    > news:aqKdk.128$...
    >> pete wrote:
    >>> if (comp > 0) {
    >>> low = middle;
    >>> } else {
    >>> high = middle;
    >>> if (comp == 0) {

    >> You are making *two* comparisons per step here, thus doubling the
    >> total number of comparisons.

    >
    > No. He is using the value returned by the comparison function twice.


    That doesn't matter, because the comparison function needs to make
    internally (at least) two comparisons to be able to return -1, 0 or 1.
    The piece of code I quoted simply highlighted this fact.

    > Your distinction might be important if the comparison operation is very
    > cheap


    In this particular case the original questions asked how many
    comparisons are required. I consider "<" and "==" to be *two*
    comparisons, even if they are applied to the same values.

    The distinction is relevant because binary search can be implemented
    with only one comparison (<) per step (in fact, equality comparison is
    not needed at all in order to implement a fully-working binary search).
    Thus this distinction is quite relevant with regard to the original
    questions.
     
    Juha Nieminen, Jul 12, 2008
    #12
  13. writes:

    > Lew writes:
    >> > As long as both low and high stay below Integer.MAX_VALUE/2, or to put
    >> > it another way, as long as the value position is below
    >> > Integer.MAX_VALUE/2.

    >
    > Ben Bacarisse wrote:
    >> Not if you do, as I did, and turn the pseudo-code into C with low and
    >> high unsigned (size_t is a good choice).  Then you get no overflow
    >> issues.  A good values for "not_found" is then N.

    >
    > Given the OP's original distribution to a Java newsgroup and not a C
    > newsgroup, I looked at the problem strictly from a Java perspective/
    >
    >> I don't know if Java has a non-overflowing integer type.

    >
    > It does not, by design.
    >
    > But surely size_t does overflow in C? Unsignedness doesn't prevent
    > overflow, it just shifts the trouble point.


    Well it does (prevent overflow) but that is a matter of C's particular
    terminology. C's unsigned types don't "overflow" because that term
    is reserved for what happens to other types like signed ints.

    You are quite right that writing:

    size_t low = 0, high = N;
    ...
    size_t mid = (low + high)/2;

    shifts the problem. It is now not "overflow" (which in C can cause
    pretty much anything) but getting -- absolutely predictably -- the
    wrong answer! The canonical way to write this correctly is:

    size_t mid = low + (high - low)/2;

    I got too hung up on the word to see what you were getting at and,
    frankly, I should have got it right away. It is, quite literally, one
    of the oldest bugs around.

    The original posted code isn't really wrong. If it can be seem as
    pseudo code the arithmetic might be mathematical arithmetic.

    --
    Ben.
     
    Ben Bacarisse, Jul 12, 2008
    #13
  14. Ray Leon

    Ray Leon Guest

    I did run the code that Pete created. The actual book is a beginners
    programming text, and is pseudocode. Can I assume that since the problem
    states
    2. Consider the array consisting of 7 elements sorted in ascending order.
    What is the Maximum number of comparisons that need to be done to find any
    given element using:

    a. Sequential search (10 points)
    b. Binary search (10 points)
    The key word being ANY GIVEN ELEMENT so the Pete's code I ran and looks like
    it ran eight (8) comparisons. I assume that my answer should be seven (7)
    since the array should only consist of seven elements.



    Ray

    "Ben Bacarisse" <> wrote in message
    news:...
    > Lew <> writes:
    >
    >> popeyerayaz <> writes:
    >>>> low = 0
    >>>> high = N
    >>>> while (low < high) {
    >>>> mid = (low + high)/2;
    >>>> if (A[mid] < value)
    >>>> low = mid + 1;
    >>>> else
    >>>> //can't be high = mid-1: here A[mid] >= value,
    >>>> //so high can't be < mid if A[mid] == value
    >>>> high = mid;
    >>>> }
    >>>>
    >>>> if (low < N) and (A[low] == value)
    >>>> return low
    >>>> else
    >>>> return not_found
    >>>>
    >>>> any help greatly appreciated.

    >>
    >> Weird to see C code in a message thread that was apparently geared to
    >> the Java community.

    >
    > Actually it is not C either. I assumed it was pseudo-code (though it
    > is not a million miles from either, style issues aside).
    >
    >> Ben Bacarisse wrote:
    >>> It looks fine to me. Maybe what you are running is not quite the same
    >>> code (or maybe I've missed a bug in it, but I tested it *and* reasoned
    >>> about it!).

    >>
    >> As long as both low and high stay below Integer.MAX_VALUE/2, or to put
    >> it another way, as long as the value position is below
    >> Integer.MAX_VALUE/2.

    >
    > Not if you do, as I did, and turn the pseudo-code into C with low and
    > high unsigned (size_t is a good choice). Then you get no overflow
    > issues. A good values for "not_found" is then N.
    >
    > I don't know if Java has a non-overflowing integer type.
    >
    > --
    > Ben.
     
    Ray Leon, Jul 12, 2008
    #14
  15. Ray Leon

    user923005 Guest

    On Jul 11, 10:22 pm, (Richard Harter) wrote:
    > On Fri, 11 Jul 2008 19:39:55 -0700, "Dann Corbit"
    >
    >
    >
    >
    >
    > <> wrote:
    > >"Richard Harter" <> wrote in message
    > >news:...
    > >> On Fri, 11 Jul 2008 18:15:14 -0700, "Dann Corbit"
    > >> <> wrote:

    >
    > >>>"Lew" <> wrote in message
    > >>>news:...
    > >>>> Juha Nieminen wrote:
    > >>>> pete wrote:
    > >>>>>>>>             if (comp > 0) {

    >
    > >>>> 'if' => comparison number one.

    >
    > >>>>>>>>                 low = middle;
    > >>>>>>>>             } else {
    > >>>>>>>>                 high = middle;
    > >>>>>>>>                 if (comp == 0) {

    >
    > >>>> 'if' => comparison number two.

    >
    > >>>> "Juha Nieminen" wrote ...
    > >>>>>>>  You are making *two* comparisons per step here, thus doubling the
    > >>>>>>> total number of comparisons.

    >
    > >>>> Dann Corbit wrote:
    > >>>>>> No.  He is using the value returned by the comparison function twice.

    >
    > >>>> In two comparisons.

    >
    > >>>> It's pretty obvious.

    >
    > >>>In sorting, the comparison count is the number of times the comparison
    > >>>function is called.  I can obviously see how decisions have been made with
    > >>>the return of the comparison function.

    >
    > >> With all due respect, this just won't do.  Yes, you can count the
    > >> number of calls to a comparison function, and that is a
    > >> convenient thing to do.  Quite often that is the appropriate
    > >> thing to do.  Still, a ternary valued comparison function
    > >> delivers log2(3) bits of information rather than one bit.  What
    > >> you are doing in the code is exploiting the fact that the cost of
    > >> doing comparisons on that ternary value might be cheap compared
    > >> to the cost of doing comparisons on the original data, and that
    > >> quite often detecting equality during the course of a comparison
    > >> is cheap.  These considerations are programming tricks rather
    > >> than mathematics.

    >
    > >Using a ternary comparison is standard in the C language and expected by
    > >standard library functions.

    >
    > [snip quotations from manuals]
    >
    > I'm sorry, I actually roared with laughter when reading your
    > response.  Bad of me, of course, but still.  This thread is not
    > posted to comp.lang.c, it is a thread that is cross posted to
    > comp.programming and comp.lang.java.programmer.  The
    > idiosyncracies of the C language are only marginally relevant,
    > and doing computer science does not consist of quoting from
    > language manuals.


    It was nothing more than an explanation of why a tertiary comparison
    is not surprising.
     
    user923005, Jul 12, 2008
    #15
  16. Please don't top-post. I've edited out most of the message you
    replied to and moved you comments to the bottom.

    "Ray Leon" <> writes:
    > "Ben Bacarisse" <> wrote in message
    > news:...

    <snip>
    >>> popeyerayaz <> writes:
    >>>>> low = 0
    >>>>> high = N
    >>>>> while (low < high) {
    >>>>> mid = (low + high)/2;
    >>>>> if (A[mid] < value)
    >>>>> low = mid + 1;
    >>>>> else
    >>>>> //can't be high = mid-1: here A[mid] >= value,
    >>>>> //so high can't be < mid if A[mid] == value
    >>>>> high = mid;
    >>>>> }
    >>>>>
    >>>>> if (low < N) and (A[low] == value)
    >>>>> return low
    >>>>> else
    >>>>> return not_found
    >>>>>
    >>>>> any help greatly appreciated.

    <snip>
    >>> Ben Bacarisse wrote:
    >>>> It looks fine to me.

    <snip>
    > I did run the code that Pete created. The actual book is a beginners
    > programming text, and is pseudocode. Can I assume that since the
    > problem states
    > 2. Consider the array consisting of 7 elements sorted in ascending
    > order. What is the Maximum number of comparisons that need to be done
    > to find any given element using:
    >
    > a. Sequential search (10 points)
    > b. Binary search (10 points)
    > The key word being ANY GIVEN ELEMENT so the Pete's code I ran and
    > looks like it ran eight (8) comparisons. I assume that my answer
    > should be seven (7) since the array should only consist of seven
    > elements.


    Pete's code was slightly differently organised but I don't see how you
    get 8. It is usual to count only the comparisons between elements and
    not to add in those involving counters etc that are there just to run
    the loops and so on. Is that what you are counting?

    [I've set followup-to: comp.programming since this is not really about
    Java as far as I can see.]

    --
    Ben.
     
    Ben Bacarisse, Jul 12, 2008
    #16
  17. Ray Leon

    Roedy Green Guest

    On Thu, 10 Jul 2008 11:35:21 -0700, "Ray Leon" <>
    wrote, quoted or indirectly quoted someone who said :

    >
    >I have completed a quiz and just want feedback on any possible mistake I
    >have made if any. Any help is greatly appreciated. I think I have the
    >correct answers for the following questions:


    see http://mindprod.com/jgloss/binarysearch.html

    Write the code, and add instrumentation to count how often compare is
    called.

    See also http://mindprod.com/jgloss/comparator.html
    http://mindprod.com/jgloss/comparable.html
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Jul 12, 2008
    #17
  18. pete wrote:
    > I can't can't get as many as 4 to find any element either.


    Because you are not counting all the comparisons you are making.

    > if (A[mid] < value) {
    > low = mid;
    > } else {
    > high = mid;
    > if (A[mid] == value) {


    You are making *two* comparisons there, not one.
     
    Juha Nieminen, Jul 12, 2008
    #18
  19. Dann Corbit wrote:
    > So when you want to know how many comparisons a sort or search is
    > performing, you count every relational operator used in the program?


    No, you count the number of comparisons applied to the elements of the
    array. In all these examples *two* comparisons with the elements of the
    array are performed at each step.

    One suggestion cleverly tried to disguise the comparison into looking
    just like one by making it a function call which performs the comparison
    with the array element. However, the function in question must use at
    least two comparisons with the element in order to be able to return one
    of three possible values.

    Again: Binary search *can* be implemented with one single comparison
    per step. The equality comparison is not strictly needed.
     
    Juha Nieminen, Jul 12, 2008
    #19
  20. Dann Corbit wrote:
    > To Juha:
    > He could have written comparison as:
    >
    > int comparison(const void *arg1, const void *arg2)
    > {
    > ++Comps;
    > return *(const int *)arg2 - *(const int *)arg1;
    > }


    That can only be applied if you know the elements are integers.

    I understood the original questions to be more generic in nature, and
    the given arrays using integers to be just an example. You could
    substitute the integers with anything else that can be comparable for
    inequality.

    You can't make a generic binary search which assumes you can perform a
    substraction of the elements. The only thing you can assume is that you
    can compare if one of them is less than the other.

    The fact remains, if you want to compare for < and ==, that makes two
    comparisons, and a binary search does not really need the latter, so
    it's possible to implement it with just one comparison per step (and
    thus the worst-case total number of comparisons is smaller, at least
    from a certain array size up).
     
    Juha Nieminen, Jul 12, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Albert Tu
    Replies:
    3
    Views:
    554
    Bengt Richter
    Mar 10, 2005
  2. lei
    Replies:
    6
    Views:
    487
  3. Timmy
    Replies:
    5
    Views:
    494
  4. Replies:
    9
    Views:
    466
    Keith Thompson
    Jul 3, 2009
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,233
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page