# 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

2. ### Morris KeesanGuest

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

3. ### James KuyperGuest

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
4. ### NobodyGuest

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
5. ### scottGuest

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
6. ### jameskuyperGuest

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

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
8. ### Barry SchwarzGuest

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

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
10. ### Keith ThompsonGuest

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