beginner with C : quick search or binary search help needed with forand while

Discussion in 'C Programming' started by bpascal123@googlemail.com, Jul 1, 2009.

  1. Guest

    Hi,

    I'd like to know how to use well FOR et WHILE. I post this script
    below so to illustrate a quicksort program :

    1st : it doesn't work

    2nd : I 'd like to see how to replace for by while or while by for ---
    for that specific program (I couldn't figure this out altough I spent
    a lot of time on this - but the programm I'm doing so from is not even
    fully working, I made it work once by changing variable POS :

    Everything below ( plz don't include functions, for the time i'm
    spending to learn, i'd like to deepen my knowledge of basic structures
    and arrays...)


    ===========================================
    START HERE
    ===========================================

    main()
    {
    /* Déclarations */
    int A[50]; /* table */
    int VAL; /* value */
    int POS; /* position */
    int N; /* dimension */
    int I; /* indice courant */
    int INF, MIL, SUP; /* limits */


    printf("\n\n===============\n\n") ;

    printf("How many numbers in the array ? ") ;
    scanf("%d", &N);

    for (I=0; I<N; I++)
    {
    A = op * 10 / 8 + 6 ;
    op = A ;
    printf("%4d", A) ;
    }

    printf("\n\n===============\n\n") ;


    printf("Enter a number you are looking for : ");
    scanf("%d", &VAL );

    /* Display the array */

    printf("Array entered is : \n");

    for (I=0; I<N; I++)
    printf("%d ", A);
    printf("\n");

    /* Set search limits*/

    INF=0;
    SUP=N-1;

    /* Search the number */

    POS=-1;

    while ((INF<=SUP) && (POS==-1))
    {
    MIL=(SUP+INF)/2;
    if (VAL < A[MIL])
    SUP=MIL-1;
    else if (VAL > A[MIL])
    INF=MIL+1;
    else
    POS=MIL;
    }

    /* Print the result of the search */

    if (POS==-1)
    printf("No match\n");
    else
    printf("Value is %d and its position %d. \n",
    VAL, POS);

    return 0;
    ===========================================
    ENDS HERE ( with the last "main" bracket )
    ===========================================


    Below it the same one but fully working (i didn't translate it as
    variables remain the same)


    ===========================================
    START HERE
    ===========================================

    #include <stdio.h>
    main()
    {
    /* Déclarations */
    int A[50]; /* tableau donné */
    int VAL; /* valeur à rechercher */
    int POS; /* position de la valeur */
    int N; /* dimension */
    int I; /* indice courant */

    /* Saisie des données */

    printf("Dimension du tableau (max.50) : ");
    scanf("%d", &N );

    for (I=0; I<N; I++)
    {
    printf("Elément %d : ", I);
    scanf("%d", &A);
    }
    printf("Elément à rechercher : ");
    scanf("%d", &VAL );

    /* Affichage du tableau */

    printf("Tableau donné : \n");

    for (I=0; I<N; I++)
    printf("%d ", A);
    printf("\n");

    /* Recherche de la position de la valeur */
    POS = -1;

    for (I=0 ; (I<N)&&(POS==-1) ; I++)
    if (A==VAL)
    POS=I;

    /* Edition du résultat */

    if (POS==-1)
    printf("La valeur recherchée ne se trouve pas "
    "dans le tableau.\n");
    else
    printf("La valeur %d se trouve à la position %d. \n",
    VAL, POS);

    return 0;

    ===========================================
    ENDS HERE ( with the last "main" bracket )
    ===========================================

    Please focus your help just on FOR and WHILE, so far I can't deal with
    ANSI or NON ANSI issues for scanf and so on as I'd really like to
    first understand such easy loop which I think are essentials.

    Many thanks if you can take me out of that :

    Pascal
    , Jul 1, 2009
    #1
    1. Advertising

  2. Re: beginner with C : quick search or binary search help needed withfor and while

    On Wed, 01 Jul 2009 16:08:04 -0400,
    <> wrote:


    > main()
    > {
    > /* Déclarations */
    > int A[50]; /* table */
    > int VAL; /* value */
    > int POS; /* position */
    > int N; /* dimension */
    > int I; /* indice courant */
    > int INF, MIL, SUP; /* limits */


    Don't do this (variable names in ALL UPPER CASE). It will confuse any
    other
    C programmer trying to read your code, and if you get used to it, it will
    make
    it much harder for you to read others' code. Although it's legal in the
    language, by convention variable names in C are either in all lower-case,
    or in some communities in camelCase (i.e. if a variable name consists of
    multiple words, some programmers capitalize the beginnings of the second
    and
    subsequent words. Others insert underscores).

    >
    >
    > printf("\n\n===============\n\n") ;
    >
    > printf("How many numbers in the array ? ") ;
    > scanf("%d", &N);
    >
    > for (I=0; I<N; I++)
    > {
    > A = op * 10 / 8 + 6 ;
    > op = A ;
    > printf("%4d", A) ;
    > }


    In the code you've posted, you've neglected to declare the variable op, and
    it has no initial value. Assuming a declaration with initialization for
    op,
    you can convert this "for" loop to the equivalent "while" loop (with
    variable
    names downcased):

    i = 0;
    while (i < n)
    {
    a = op * 10 / 8 + 6;
    op = a;
    printf("%4d", a);
    i++;
    }

    The general rule is that

    for (initialization; test; increment) { body; }

    is equivalent to

    initialization; while(test) { body; increment }

    except where "body;" contains any "continue" statements.


    > for (I=0; I<N; I++)
    > printf("%d ", A);


    Similarly, this could be written as
    i = 0;
    while (i < n) {
    printf("%d ", a);
    i++;
    }


    >
    > POS=-1;
    >
    > while ((INF<=SUP) && (POS==-1))
    > {
    > MIL=(SUP+INF)/2;
    > if (VAL < A[MIL])
    > SUP=MIL-1;
    > else if (VAL > A[MIL])
    > INF=MIL+1;
    > else
    > POS=MIL;
    > }


    and if you wanted to replace this while loop with a for loop, it would be

    for (pos = -1; (inf <= sup) && (pos == -1); /* no expression here */)
    {
    /* body of for same as body of while */
    }


    > Please focus your help just on FOR and WHILE, so far I can't deal with
    > ANSI or NON ANSI issues for scanf and so on as I'd really like to
    > first understand such easy loop which I think are essentials.


    I haven't bothered trying to read your program enough to figure out the
    logic or the algorithms in use. These are just conversions of one loop
    type
    to another. I would say that the loop forms you've used are those that
    most
    C programmers would use. I can't think of a reason why anyone would want
    to use
    while loops where you've used for loops, or vice versa.
    Morris Keesan, Jul 2, 2009
    #2
    1. Advertising

  3. James Kuyper Guest

    Re: beginner with C : quick search or binary search help needed withfor and while

    Morris Keesan wrote:
    ....
    > The general rule is that
    >
    > for (initialization; test; increment) { body; }
    >
    > is equivalent to
    >
    > initialization; while(test) { body; increment }
    >
    > except where "body;" contains any "continue" statements.


    Why do you exclude "continue;" statements? Are you saying

    for(i=0; i<5; i++) { if(a) continue;}

    is not equivalent to

    i = 0; while(i<5) { if(a) continue; i++;}

    ?

    A more accurate equivalent would be to say that

    for(initialization; test; increment) BODY

    is equivalent to

    {
    initialization;
    while(test)
    {
    BODY;
    increment;
    }
    }

    This adds the terminating ';' to 'increment' that was missing from your
    version. It also uses curly brackets '{' and '}' to more accurately
    represent the restricted scope of any identifier declared in
    'initialization'. This introduces a spurious extra level of nesting, but
    is otherwise correct.

    Most importantly, my formulation is more general, because I'm using BODY
    to represent a single statement of any type; if it's a compound
    statement, BODY includes the '{' and '}' characters. If it's a selection
    or iteration statement, it includes the associated keywords (if, else,
    for, do, while). If it's any other kind of statement, it includes the
    terminating ';'.
    James Kuyper, Jul 2, 2009
    #3
  4. Nobody Guest

    Re: beginner with C : quick search or binary search help needed with for and while

    On Thu, 02 Jul 2009 10:32:20 +0000, James Kuyper wrote:

    >> The general rule is that
    >>
    >> for (initialization; test; increment) { body; }
    >>
    >> is equivalent to
    >>
    >> initialization; while(test) { body; increment }
    >>
    >> except where "body;" contains any "continue" statements.

    >
    > Why do you exclude "continue;" statements? Are you saying
    >
    > for(i=0; i<5; i++) { if(a) continue;}
    >
    > is not equivalent to
    >
    > i = 0; while(i<5) { if(a) continue; i++;}
    >
    > ?


    Correct. The increment part of a "for" statement is executed for each pass
    of the loop, regardless of whether the loop body completes normally or is
    terminated prematurely by a "continue". With the "while" version, a
    "continue" will skip the increment.

    In your example, if any a is non-zero, the loop will never terminate.

    > A more accurate equivalent would be to say that
    >
    > for(initialization; test; increment) BODY
    >
    > is equivalent to
    >
    > {
    > initialization;
    > while(test)
    > {
    > BODY;
    > increment;
    > }
    > }


    True. But the "continue" issue still applies.
    Nobody, Jul 2, 2009
    #4
  5. scott Guest

    Re: beginner with C : quick search or binary search help needed withfor and while

    On Jul 2, 6:32 am, James Kuyper <> wrote:
    > Morris Keesan wrote:
    >
    > ...
    >
    > > The general rule is that

    >
    > >     for (initialization; test; increment) { body; }

    >
    > > is equivalent to

    >
    > >     initialization; while(test) { body; increment }

    >
    > > except where "body;" contains any "continue" statements.

    >
    > Why do you exclude "continue;" statements? Are you saying
    >
    >          for(i=0; i<5; i++) { if(a) continue;}
    >
    > is not equivalent to
    >
    >          i = 0; while(i<5) { if(a) continue; i++;}
    >
    > ?

    They are not equivalent. In the second case when the continue is hit
    the increment will not happen which means you will have yourself stuck
    in an infinite loop.
    >
    > A more accurate equivalent would be to say that
    >
    >         for(initialization; test; increment) BODY
    >
    > is equivalent to
    >
    >          {
    >               initialization;
    >               while(test)
    >               {
    >                    BODY;
    >                    increment;
    >               }
    >          }
    >
    > This adds the terminating ';' to 'increment' that was missing from your
    > version. It also uses curly brackets '{' and '}' to more accurately
    > represent the restricted scope of any identifier declared in
    > 'initialization'. This introduces a spurious extra level of nesting, but
    > is otherwise correct.
    >
    > Most importantly, my formulation is more general, because I'm using BODY
    > to represent a single statement of any type; if it's a compound
    > statement, BODY includes the '{' and '}' characters. If it's a selection
    > or iteration statement, it includes the associated keywords (if, else,
    > for, do, while). If it's any other kind of statement, it includes the
    > terminating ';'.


    Your version suffers from the same issue with continue as the other
    version. They simply are not the same in that case.
    scott, Jul 2, 2009
    #5
  6. jameskuyper Guest

    Re: beginner with C : quick search or binary search help needed withfor and while

    Nobody wrote:
    > On Thu, 02 Jul 2009 10:32:20 +0000, James Kuyper wrote:
    >
    > >> The general rule is that
    > >>
    > >> for (initialization; test; increment) { body; }
    > >>
    > >> is equivalent to
    > >>
    > >> initialization; while(test) { body; increment }
    > >>
    > >> except where "body;" contains any "continue" statements.

    > >
    > > Why do you exclude "continue;" statements? Are you saying
    > >
    > > for(i=0; i<5; i++) { if(a) continue;}
    > >
    > > is not equivalent to
    > >
    > > i = 0; while(i<5) { if(a) continue; i++;}
    > >
    > > ?

    >
    > Correct. The increment part of a "for" statement is executed for each pass
    > of the loop, regardless of whether the loop body completes normally or is
    > terminated prematurely by a "continue". With the "while" version, a
    > "continue" will skip the increment.



    You're right, and I should have realized it. I'm beginning to wonder
    whether it's worthwhile posting newsgroup messages before I've fully
    woken up in the morning.
    jameskuyper, Jul 2, 2009
    #6
  7. Guest

    Re: beginner with C : quick search or binary search help needed withfor and while

    Hi all,

    Below is a version with For I have worked out but it's not working.

    I didn't translate any lines of code but i can tell you basically what
    the program expects :

    - it first asks to enter a number which will be taken as the number of
    values in the array ;

    - then it displays an array of numbers and afterwards asks for a value
    and checks (with FOR) the position of the value in the array (i didn't
    make any controls with if to see if the value either exists or not, I
    am just focusing on making this script work---caps lock corrections
    and controls with "if" will come right next)

    But as you can, its position is not right at all.

    Could you correct it please?

    Thanks in advance

    Pascal


    #include <stdio.h>

    main()
    {
    int Tab[50] ;
    int N ;
    int MIL, INF, SUP ;
    int VAL ;
    int POS ;
    int midPOS ;
    int op ;
    int i, j ;
    int cnt = 1 ;
    int permut1 ;
    int ECRI ;

    printf("\n\n==============================\n\n") ;

    printf("Ce prg lit, affiche un tableau et y recherche une valeur et
    sa position.") ;

    printf("\n\n===============\n\n") ;

    printf("Entrez le nbr de valeurs : ") ;
    scanf("%d", &N);

    for ( i = 0 ; i < N ; i++ )
    {
    Tab = op * 10 / 8 + 6 ;
    op = Tab ;
    printf("%4d", Tab) ;
    }

    printf("\n\n===============\n\n") ;


    printf("Entrez une valeur a rechercher : \n\n") ;
    scanf("%d", &VAL ) ;

    printf("\n\n") ;


    INF = 0 ; SUP = N - 1 ;

    for ( INF = 0 ; INF <= SUP ; INF++ )
    {
    MIL=(SUP+INF)/2;

    if ( VAL < Tab[MIL] )
    POS = MIL - 1 ;

    else if ( VAL > Tab[MIL] )
    POS = MIL + 1 ;
    else
    POS = MIL ;
    ECRI = SUP + INF ;
    }

    printf("\n\n===============\n\n") ;

    printf("Tri : la position est %d . ===> %d ", POS, MIL ) ;


    printf("\n\n==============================\n\n") ;

    return 0 ;
    , Jul 2, 2009
    #7
  8. Re: beginner with C : quick search or binary search help needed with for and while

    On Wed, 1 Jul 2009 13:08:04 -0700 (PDT), ""
    <> wrote:

    >Hi,
    >
    >I'd like to know how to use well FOR et WHILE. I post this script
    >below so to illustrate a quicksort program :
    >
    >1st : it doesn't work
    >
    >2nd : I 'd like to see how to replace for by while or while by for ---
    >for that specific program (I couldn't figure this out altough I spent
    >a lot of time on this - but the programm I'm doing so from is not even
    >fully working, I made it work once by changing variable POS :
    >
    >Everything below ( plz don't include functions, for the time i'm
    >spending to learn, i'd like to deepen my knowledge of basic structures
    >and arrays...)
    >
    >
    >===========================================
    >START HERE
    >===========================================
    >


    You need to include stdio.h here also.

    >main()


    use int main(void). Implied return of int has been removed from the
    language even though many compilers still support it.

    >{
    > /* Déclarations */
    > int A[50]; /* table */
    > int VAL; /* value */
    > int POS; /* position */
    > int N; /* dimension */
    > int I; /* indice courant */
    > int INF, MIL, SUP; /* limits */
    >
    >
    > printf("\n\n===============\n\n") ;
    >
    > printf("How many numbers in the array ? ") ;
    > scanf("%d", &N);


    If you are going to let the use specify, you better make sure he
    specifies 50 or less.

    >
    > for (I=0; I<N; I++)
    > {
    > A = op * 10 / 8 + 6 ;
    > op = A ;
    > printf("%4d", A) ;
    > }
    >
    >printf("\n\n===============\n\n") ;
    >
    >
    > printf("Enter a number you are looking for : ");
    > scanf("%d", &VAL );
    >
    > /* Display the array */
    >
    > printf("Array entered is : \n");
    >
    > for (I=0; I<N; I++)
    > printf("%d ", A);
    > printf("\n");


    How does this differ from the previous for loop?

    >
    > /* Set search limits*/
    >
    > INF=0;
    > SUP=N-1;
    >
    > /* Search the number */
    >
    > POS=-1;
    >
    > while ((INF<=SUP) && (POS==-1))
    > {
    > MIL=(SUP+INF)/2;
    > if (VAL < A[MIL])


    A binary search is only useful is the array is sorted.

    > SUP=MIL-1;
    > else if (VAL > A[MIL])
    > INF=MIL+1;
    > else
    > POS=MIL;
    > }
    >
    > /* Print the result of the search */
    >
    > if (POS==-1)
    > printf("No match\n");
    > else
    > printf("Value is %d and its position %d. \n",
    > VAL, POS);
    >
    > return 0;
    >===========================================
    >ENDS HERE ( with the last "main" bracket )


    Where is the bracket (actually called a brace)?

    >===========================================
    >
    >
    >Below it the same one but fully working (i didn't translate it as
    >variables remain the same)
    >
    >
    >===========================================
    >START HERE
    >===========================================
    >
    >#include <stdio.h>
    >main()
    >{
    > /* Déclarations */
    > int A[50]; /* tableau donné */
    > int VAL; /* valeur à rechercher */
    > int POS; /* position de la valeur */
    > int N; /* dimension */
    > int I; /* indice courant */
    >
    > /* Saisie des données */
    >
    > printf("Dimension du tableau (max.50) : ");
    > scanf("%d", &N );


    You should still check.

    >
    > for (I=0; I<N; I++)
    > {
    > printf("Elément %d : ", I);
    > scanf("%d", &A);
    > }
    > printf("Elément à rechercher : ");
    > scanf("%d", &VAL );
    >
    > /* Affichage du tableau */
    >
    > printf("Tableau donné : \n");
    >
    > for (I=0; I<N; I++)
    > printf("%d ", A);
    > printf("\n");
    >
    > /* Recherche de la position de la valeur */
    > POS = -1;
    >
    > for (I=0 ; (I<N)&&(POS==-1) ; I++)
    > if (A==VAL)
    > POS=I;


    This is a sequential search and is insensitive to the order of the
    values.

    >
    > /* Edition du résultat */
    >
    > if (POS==-1)
    > printf("La valeur recherchée ne se trouve pas "
    > "dans le tableau.\n");
    > else
    > printf("La valeur %d se trouve à la position %d. \n",
    > VAL, POS);
    >
    > return 0;
    >
    >===========================================
    >ENDS HERE ( with the last "main" bracket )


    Why do you omit the brace? If anyone wants to compile your code, the
    don't want to bother fixing syntax errors.

    >===========================================
    >
    >Please focus your help just on FOR and WHILE, so far I can't deal with
    >ANSI or NON ANSI issues for scanf and so on as I'd really like to
    >first understand such easy loop which I think are essentials.


    I'm not aware of any ASCII/non-ASCII issues for %d.

    --
    Remove del for email
    Barry Schwarz, Jul 3, 2009
    #8
  9. Guest

    Re: beginner with C : quick search or binary search help needed withfor and while

    If you are going to let the use specify, you better make sure he
    specifies 50 or less.

    Yes, this is done in the printf cmd...


    A binary search is only useful is the array is sorted.

    This array is already sorted from the smallest to the greatest value.
    If it wouldn't be the case, I would insert a "permuting" loop


    Where is the bracket (actually called a brace)?

    When I copy-paste in google group usenet, the bracket is deleted by
    the browser, i think it's a security issue.


    > for (I=0 ; (I<N)&&(POS==-1) ; I++)
    > if (A==VAL)
    > POS=I;




    This is a sequential search and is insensitive to the order of the
    values.


    I know about this sequential search, but it would take in a huge
    database that's why I'd like to understand how to make search from the
    middle by comparing the mid value with the value being searched and
    then do a sequential search...I had thought it's part of the basics
    for any programers...
    , Jul 3, 2009
    #9
  10. Re: beginner with C : quick search or binary search help needed with for and while

    "" <> writes:
    > If you are going to let the use specify, you better make sure he
    > specifies 50 or less.
    >
    > Yes, this is done in the printf cmd...
    >
    >
    > A binary search is only useful is the array is sorted.
    >
    > This array is already sorted from the smallest to the greatest value.
    > If it wouldn't be the case, I would insert a "permuting" loop


    About half of the above is actually quoted from a previous article
    by Barry Schwarz, but the quotations aren't marked in any way.

    The Google Groups interface will actually include the article you're
    responding to, properly quoted. Please don't override that
    feature.

    > Where is the bracket (actually called a brace)?
    >
    > When I copy-paste in google group usenet, the bracket is deleted by
    > the browser, i think it's a security issue.


    That's implausible. Google Groups users manage to copy-and-paste C
    code all the time, and I've never seen a problem with curly braces.
    You probably just didn't copy-and-paste the entire program.
    Mistakes happen, and they aren't a huge deal.

    [...]

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Jul 3, 2009
    #10
    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. JKop
    Replies:
    11
    Views:
    856
  2. tsunami
    Replies:
    3
    Views:
    332
    Mark P
    Aug 6, 2005
  3. j1mb0jay
    Replies:
    5
    Views:
    2,500
    Tom Anderson
    May 25, 2008
  4. Ray Leon
    Replies:
    25
    Views:
    1,560
    John W Kennedy
    Jul 13, 2008
  5. Bogdan

    Binary tree search vs Binary search

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

Share This Page