## C and C++

Moderators: None (Apply to moderate this forum)
Number of threads: 28691
Number of posts: 94711

This Forum Only

Sequential Search / Linear Search Posted by tokoG on 26 Jun 2006 at 10:28 PM
Hi another question regarding the searches. (As I am studying this topic now)

Linear search is sequential search and it's worst case which means the longest time it takes to search array with the size N is N times because it has to visit one by one. The best case is one time if the first data was happened to be the target data to be found.

But... how about three-dimentional array of size N?
The worst and best?

I dont think I've ever learn three dimentional array but I assume it's like,

array[N][N][N]

And I don't think in either case one-dimentinal or three-dimentional doesnt change the length of time to search? Worst for size N for three dimentional is still N time and the best is still one time I reckon?

Is that so??
Re: Sequential Search / Linear Search Posted by tsagld on 27 Jun 2006 at 12:03 AM
: Hi another question regarding the searches. (As I am studying this topic now)
:
: Linear search is sequential search and it's worst case which means the longest time it takes to search array with the size N is N times because it has to visit one by one. The best case is one time if the first data was happened to be the target data to be found.
:
: But... how about three-dimentional array of size N?
: The worst and best?
:
: I dont think I've ever learn three dimentional array but I assume it's like,
:
: array[N][N][N]
:
: And I don't think in either case one-dimentinal or three-dimentional doesnt change the length of time to search? Worst for size N for three dimentional is still N time and the best is still one time I reckon?
:
: Is that so??

No.
array[N][N][N] has n*n*n elements, so worst case is n*n*n and best case is still one if the element to search for is at array[0][0][0].

Greets,
Eric Goldstein
http://www.gvh-maatwerk.nl

Re: Sequential Search / Linear Search Posted by tokoG on 27 Jun 2006 at 12:26 AM
:
: No.
: array[N][N][N] has n*n*n elements, so worst case is n*n*n and best case is still one if the element to search for is at array[0][0][0].
:

Hi Eric

I am not sure what three dimentional array is.
Is it the.. array[string length][column][row] though?

In that case, if N=2, it would be array[2][2][2] I think.
Is one of the [N] is the length of the string, why would it take 2*2*2 = 8 times to search?

Re: Sequential Search / Linear Search Posted by tsagld on 27 Jun 2006 at 2:57 AM
: :
: : No.
: : array[N][N][N] has n*n*n elements, so worst case is n*n*n and best case is still one if the element to search for is at array[0][0][0].
: :
:
: Hi Eric
:
: I am not sure what three dimentional array is.
: Is it the.. array[string length][column][row] though?
:
: In that case, if N=2, it would be array[2][2][2] I think.
: Is one of the [N] is the length of the string, why would it take 2*2*2 = 8 times to search?
:
:

A multi-dimensional array doesn't have a specific meaning. You use it whenever you think is appropriate.
Think of it as follows:
- A one-dimensional array is an array of elements;
- A two-dimensional array is an array where each element is an array of elements;
- A three-dimensional array is an array where each element is an array, of which each element is an array of elements;
- A four-dimensional array is .....
etc.

An example:
Suppose you want to store outside temperatures on a regular basis:
```//store temperatures by hour, for one day:
int temperatures[24];

//to get the temperature at noon:
int temp = temperatures[12];
```

Obvious, isn't it?

Now you decide you want to keep track of the temperatures for a whole month:
```//store temperatures by hour, by day for one month:
int temperatures[31][24];

//to get the temperature at day 9, 07:00 AM:
int temp = temperatures[8][7]; //note that I use 8, because array-indices are zero-based in C++
```

Now you decide to keep track of the temperatures for a whole year:
```//store temperatures by hour, by day, by month for one year:
int temperatures[12][31][24];

//to get the temperature at May 23rd, 04:00 PM:
int temp = temperatures[4][22][16];
```

You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:
```//store temperatures by hour, by day, by month for one year:
int temperatures[100][12][31][24];

//to get the temperature at May 23rd 1988, 04:00 PM:
int temp = temperatures[88][4][22][16];
```

Take this 4-dimensional array, and suppose you would want to know if the temperature raised above 100 degrees at some time.
The array contains 100*12*31*24 = 892,800 temperatures. So you need 892,800 comparisons worst case, or one comparision best case:

```for (int y=0; y<100; y++)
{
for (int m=0; m<12; m++)
{
for (int d=0; d<31; d++)
{
for (int h=0; h<24; h++)
{
if (temperatures[y][m][d][h] > 100)
{
//found!
}
}
}
}
}
```

Greets,
Eric Goldstein
http://www.gvh-maatwerk.nl

Re: Sequential Search / Linear Search Posted by Lundin on 27 Jun 2006 at 5:00 AM
: : :
: : : No.
: : : array[N][N][N] has n*n*n elements, so worst case is n*n*n and best case is still one if the element to search for is at array[0][0][0].
: : :
: :
: : Hi Eric
: :
: : I am not sure what three dimentional array is.
: : Is it the.. array[string length][column][row] though?
: :
: : In that case, if N=2, it would be array[2][2][2] I think.
: : Is one of the [N] is the length of the string, why would it take 2*2*2 = 8 times to search?
: :
: :

:
: A multi-dimensional array doesn't have a specific meaning. You use it whenever you think is appropriate.
: Think of it as follows:
: - A one-dimensional array is an array of elements;
: - A two-dimensional array is an array where each element is an array of elements;
: - A three-dimensional array is an array where each element is an array, of which each element is an array of elements;
: - A four-dimensional array is .....
: etc.
:
: An example:
: Suppose you want to store outside temperatures on a regular basis:
:
```: //store temperatures by hour, for one day:
: int temperatures[24];
:
: //to get the temperature at noon:
: int temp = temperatures[12];
: ```

: Obvious, isn't it?
:
: Now you decide you want to keep track of the temperatures for a whole month:
:
```: //store temperatures by hour, by day for one month:
: int temperatures[31][24];
:
: //to get the temperature at day 9, 07:00 AM:
: int temp = temperatures[8][7]; //note that I use 8, because array-indices are zero-based in C++
: ```

:
: Now you decide to keep track of the temperatures for a whole year:
:
```: //store temperatures by hour, by day, by month for one year:
: int temperatures[12][31][24];
:
: //to get the temperature at May 23rd, 04:00 PM:
: int temp = temperatures[4][22][16];
: ```

:
: You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:
:
```: //store temperatures by hour, by day, by month for one year:
: int temperatures[100][12][31][24];
:
: //to get the temperature at May 23rd 1988, 04:00 PM:
: int temp = temperatures[88][4][22][16];
: ```

:
: Take this 4-dimensional array, and suppose you would want to know if the temperature raised above 100 degrees at some time.
: The array contains 100*12*31*24 = 892,800 temperatures. So you need 892,800 comparisons worst case, or one comparision best case:
:
:
```: for (int y=0; y<100; y++)
: {
:   for (int m=0; m<12; m++)
:   {
:     for (int d=0; d<31; d++)
:     {
:       for (int h=0; h<24; h++)
:       {
:         if (temperatures[y][m][d][h] > 100)
:         {
:           //found!
:         }
:       }
:     }
:   }
: }
: ```

:
: Greets,
: Eric Goldstein
: http://www.gvh-maatwerk.nl
:
:

There are are some problems with multi-dimensional arrays that one should be aware of:

1) You must specify the size of every dimension except the first when writing a function taking them as parameter. So it is not easy to pass them to general purpose functions.

2) You can't typecast between multi-dimensional arrays and pointer-to-pointers. If you use dynamicly allocated arrays, this will cause lots of trouble, since they are always allocated using pointer-to-pointer. Meaning you can't typecast between staticly and dynamicly multi-dimensional arrays.

If the above causes trouble in the implementation, skip the multi-dimensions and "mangle" the array to one dimension instead.
Re: Sequential Search / Linear Search Posted by tsagld on 27 Jun 2006 at 6:14 AM
: : : :
: : : : No.
: : : : array[N][N][N] has n*n*n elements, so worst case is n*n*n and best case is still one if the element to search for is at array[0][0][0].
: : : :
: : :
: : : Hi Eric
: : :
: : : I am not sure what three dimentional array is.
: : : Is it the.. array[string length][column][row] though?
: : :
: : : In that case, if N=2, it would be array[2][2][2] I think.
: : : Is one of the [N] is the length of the string, why would it take 2*2*2 = 8 times to search?
: : :
: : :

: :
: : A multi-dimensional array doesn't have a specific meaning. You use it whenever you think is appropriate.
: : Think of it as follows:
: : - A one-dimensional array is an array of elements;
: : - A two-dimensional array is an array where each element is an array of elements;
: : - A three-dimensional array is an array where each element is an array, of which each element is an array of elements;
: : - A four-dimensional array is .....
: : etc.
: :
: : An example:
: : Suppose you want to store outside temperatures on a regular basis:
: :
```: : //store temperatures by hour, for one day:
: : int temperatures[24];
: :
: : //to get the temperature at noon:
: : int temp = temperatures[12];
: : ```

: : Obvious, isn't it?
: :
: : Now you decide you want to keep track of the temperatures for a whole month:
: :
```: : //store temperatures by hour, by day for one month:
: : int temperatures[31][24];
: :
: : //to get the temperature at day 9, 07:00 AM:
: : int temp = temperatures[8][7]; //note that I use 8, because array-indices are zero-based in C++
: : ```

: :
: : Now you decide to keep track of the temperatures for a whole year:
: :
```: : //store temperatures by hour, by day, by month for one year:
: : int temperatures[12][31][24];
: :
: : //to get the temperature at May 23rd, 04:00 PM:
: : int temp = temperatures[4][22][16];
: : ```

: :
: : You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:
: :
```: : //store temperatures by hour, by day, by month for one year:
: : int temperatures[100][12][31][24];
: :
: : //to get the temperature at May 23rd 1988, 04:00 PM:
: : int temp = temperatures[88][4][22][16];
: : ```

: :
: : Take this 4-dimensional array, and suppose you would want to know if the temperature raised above 100 degrees at some time.
: : The array contains 100*12*31*24 = 892,800 temperatures. So you need 892,800 comparisons worst case, or one comparision best case:
: :
: :
```: : for (int y=0; y<100; y++)
: : {
: :   for (int m=0; m<12; m++)
: :   {
: :     for (int d=0; d<31; d++)
: :     {
: :       for (int h=0; h<24; h++)
: :       {
: :         if (temperatures[y][m][d][h] > 100)
: :         {
: :           //found!
: :         }
: :       }
: :     }
: :   }
: : }
: : ```

: :
: : Greets,
: : Eric Goldstein
: : http://www.gvh-maatwerk.nl
: :
: :
:
:
: There are are some problems with multi-dimensional arrays that one should be aware of:
:
: 1) You must specify the size of every dimension except the first when writing a function taking them as parameter. So it is not easy to pass them to general purpose functions.
:
: 2) You can't typecast between multi-dimensional arrays and pointer-to-pointers. If you use dynamicly allocated arrays, this will cause lots of trouble, since they are always allocated using pointer-to-pointer. Meaning you can't typecast between staticly and dynamicly multi-dimensional arrays.
:
: If the above causes trouble in the implementation, skip the multi-dimensions and "mangle" the array to one dimension instead.
:
What Lundin probably means by 'mangling' is to store all elements in one dimension. Following my example:

Store the temperatures for a whole century in a one-dimensional array:
```//store temperatures by hour, by day, by month for one year:
int temperatures[100*12*31*24];

//to get the temperature at May 23rd 1988, 04:00 PM:
int temp = temperatures[88*12*31*24 + 4*31*24 + 23*24 + 4];
```

Greets,
Eric Goldstein
http://www.gvh-maatwerk.nl

Re: Sequential Search / Linear Search Posted by Lundin on 27 Jun 2006 at 6:40 AM
: : : : :
: : : : : No.
: : : : : array[N][N][N] has n*n*n elements, so worst case is n*n*n and best case is still one if the element to search for is at array[0][0][0].
: : : : :
: : : :
: : : : Hi Eric
: : : :
: : : : I am not sure what three dimentional array is.
: : : : Is it the.. array[string length][column][row] though?
: : : :
: : : : In that case, if N=2, it would be array[2][2][2] I think.
: : : : Is one of the [N] is the length of the string, why would it take 2*2*2 = 8 times to search?
: : : :
: : : :

: : :
: : : A multi-dimensional array doesn't have a specific meaning. You use it whenever you think is appropriate.
: : : Think of it as follows:
: : : - A one-dimensional array is an array of elements;
: : : - A two-dimensional array is an array where each element is an array of elements;
: : : - A three-dimensional array is an array where each element is an array, of which each element is an array of elements;
: : : - A four-dimensional array is .....
: : : etc.
: : :
: : : An example:
: : : Suppose you want to store outside temperatures on a regular basis:
: : :
```: : : //store temperatures by hour, for one day:
: : : int temperatures[24];
: : :
: : : //to get the temperature at noon:
: : : int temp = temperatures[12];
: : : ```

: : : Obvious, isn't it?
: : :
: : : Now you decide you want to keep track of the temperatures for a whole month:
: : :
```: : : //store temperatures by hour, by day for one month:
: : : int temperatures[31][24];
: : :
: : : //to get the temperature at day 9, 07:00 AM:
: : : int temp = temperatures[8][7]; //note that I use 8, because array-indices are zero-based in C++
: : : ```

: : :
: : : Now you decide to keep track of the temperatures for a whole year:
: : :
```: : : //store temperatures by hour, by day, by month for one year:
: : : int temperatures[12][31][24];
: : :
: : : //to get the temperature at May 23rd, 04:00 PM:
: : : int temp = temperatures[4][22][16];
: : : ```

: : :
: : : You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:
: : :
```: : : //store temperatures by hour, by day, by month for one year:
: : : int temperatures[100][12][31][24];
: : :
: : : //to get the temperature at May 23rd 1988, 04:00 PM:
: : : int temp = temperatures[88][4][22][16];
: : : ```

: : :
: : : Take this 4-dimensional array, and suppose you would want to know if the temperature raised above 100 degrees at some time.
: : : The array contains 100*12*31*24 = 892,800 temperatures. So you need 892,800 comparisons worst case, or one comparision best case:
: : :
: : :
```: : : for (int y=0; y<100; y++)
: : : {
: : :   for (int m=0; m<12; m++)
: : :   {
: : :     for (int d=0; d<31; d++)
: : :     {
: : :       for (int h=0; h<24; h++)
: : :       {
: : :         if (temperatures[y][m][d][h] > 100)
: : :         {
: : :           //found!
: : :         }
: : :       }
: : :     }
: : :   }
: : : }
: : : ```

: : :
: : : Greets,
: : : Eric Goldstein
: : : http://www.gvh-maatwerk.nl
: : :
: : :
: :
: :
: : There are are some problems with multi-dimensional arrays that one should be aware of:
: :
: : 1) You must specify the size of every dimension except the first when writing a function taking them as parameter. So it is not easy to pass them to general purpose functions.
: :
: : 2) You can't typecast between multi-dimensional arrays and pointer-to-pointers. If you use dynamicly allocated arrays, this will cause lots of trouble, since they are always allocated using pointer-to-pointer. Meaning you can't typecast between staticly and dynamicly multi-dimensional arrays.
: :
: : If the above causes trouble in the implementation, skip the multi-dimensions and "mangle" the array to one dimension instead.
: :
: What Lundin probably means by 'mangling' is to store all elements in one dimension. Following my example:
:
: Store the temperatures for a whole century in a one-dimensional array:
:
```: //store temperatures by hour, by day, by month for one year:
: int temperatures[100*12*31*24];
:
: //to get the temperature at May 23rd 1988, 04:00 PM:
: int temp = temperatures[88*12*31*24 + 4*31*24 + 23*24 + 4];
: ```

:
:
: Greets,
: Eric Goldstein
: http://www.gvh-maatwerk.nl
:
:
:

Yep. Looks more inefficient at first sight, but the program would need to calculate that offset in runtime anyway, so the result should be the same.

(A smart compiler would optimize this particular example to an absolute address instead, since the offset is known at compile-time. But if we had variables instead of numbers, it would be force to do it in runtime)
to: Eric and Lundin Posted by tokoG on 27 Jun 2006 at 9:38 PM
Wow, what a great and throughly explanation!!
The best way to picturise two,three, multi dimentional array!!

For the last post of Eric, to get the tamperature of May, 23rd, 1998, 16:00pm, isn't it;

[88*12*31*24 + 4*31*24 + 22*24 + 16]

insted?

How about in binary search?
one-dimentional array search and two-dimentional array search. Worst case and the best case.

I think the best case for one-dimentional is the one time for both dimentions. Just the root node happens to be the targeted one.
For worst case, it has to go all the way down to the leaf node which means I think the one level of comparison is counted as one time for example..

root node: contains numeric value 5 ...........level 1
left of the root node: 3 ......................level 2
left of the root node: 2 .......................level 3
right of the root node: 4.......................level 3

So, to search for numeric value (as a key also) 4 takes 3 comparison for the binary tree size of 3.

So for the binary search the worst case I think for size N[/italic] is N times I reckon? Wihch is the hight of the tree

But then, what is the TWO-DIMENTIONAL binary tree???

Re: to: Eric and Lundin Posted by tsagld on 28 Jun 2006 at 5:35 AM
This message was edited by tsagld at 2006-6-28 5:36:0

: Wow, what a great and throughly explanation!!
: The best way to picturise two,three, multi dimentional array!!
:
: For the last post of Eric, to get the tamperature of May, 23rd, 1998, 16:00pm, isn't it;
:
: [88*12*31*24 + 4*31*24 + 22*24 + 16]
:
: insted?

Yes, you're right. You got the idea...

:
:
: How about in binary search?
: one-dimentional array search and two-dimentional array search. Worst case and the best case.
:
:
: I think the best case for one-dimentional is the one time for both dimentions. Just the root node happens to be the targeted one.
: For worst case, it has to go all the way down to the leaf node which means I think the one level of comparison is counted as one time for example..
:
: root node: contains numeric value 5 ...........level 1
: left of the root node: 3 ......................level 2
: left of the root node: 2 .......................level 3
: right of the root node: 4.......................level 3
:
: So, to search for numeric value (as a key also) 4 takes 3 comparison for the binary tree size of 3.
:
: So for the binary search the worst case I think for size N[/italic] is N times I reckon? Wihch is the hight of the tree
:

:
: But then, what is the TWO-DIMENTIONAL binary tree???

Binary search reduces the search range by 50% on each iteration.
- after iteration 1, 6 elements left
- after iteration 2, 3 elements left
- after iteration 3, 2 elements left
- after iteration 4, 1 elements left->done.
Worst case is 4 in this case.
In general, worst case is log(n) (base 2). Worst case for
1,000,000,000 elements is only 30!!! Far better than lineair.
The only thing is that binary search only works when the array is sorted.
Best case stays 1 for all algorithms.

Greets,
Eric Goldstein
http://www.gvh-maatwerk.nl

Re: to: Eric and Lundin Posted by tokoG on 28 Jun 2006 at 9:52 PM
:
: Binary search reduces the search range by 50% on each iteration.
: - after iteration 1, 6 elements left
: - after iteration 2, 3 elements left
: - after iteration 3, 2 elements left
: - after iteration 4, 1 elements left->done.
: Worst case is 4 in this case.
: In general, worst case is log(n) (base 2). Worst case for
: 1,000,000,000 elements is only 30!!! Far better than lineair.
: The only thing is that binary search only works when the array is sorted.
: Best case stays 1 for all algorithms.
:

Hi Eric

Thanks for the advice!
The calculation gave me 3.5... so aounded up to 4.
So for 12 elements the worst case is to itarate 4 times toreach the target.

But, what is the two dimentiona array in the binary search?
When you said binary search I thought it's about the search in the binary tree. But,,, is two dimensional array can be searched binary?(Dont know what it means..) or, are there any tow dimentional binary trees??

Sorry, it's the question on my little assignment and I've never heard two dimentional binary trees or the arrays to be searched by binary method..?
Re: to: Eric and Lundin Posted by tsagld on 28 Jun 2006 at 11:55 PM
Binary search is just an algorithm. You can use it on any datastructure you like, as long as the structure is sorted on the key you search for.
Don't think that arrays and search-algorithms are closely related.

If your two-dimensional array is sorted, sure you can do binary search on it. It is just a way to find something in a collection of somethings.

For an explanation of binary search, suppose you want to find the name 'Johnson' in a phone-book of 1,000 pages by hand.
You would open the book somewhere in the middle. You will see immediately if you need to go back- or forward, thus reducing the candidates by 50%.
You continue like that. If you do a perfect search and go to the exact middle always, you will see no more than 10 pages before you find the name.

Greets,
Eric Goldstein
http://www.gvh-maatwerk.nl

Re: to: Eric and Lundin Posted by tokoG on 30 Jun 2006 at 12:10 AM
: Binary search is just an algorithm. You can use it on any datastructure you like, as long as the structure is sorted on the key you search for.
: Don't think that arrays and search-algorithms are closely related.
:
: If your two-dimensional array is sorted, sure you can do binary search on it. It is just a way to find something in a collection of somethings.
:
: For an explanation of binary search, suppose you want to find the name 'Johnson' in a phone-book of 1,000 pages by hand.
: You would open the book somewhere in the middle. You will see immediately if you need to go back- or forward, thus reducing the candidates by 50%.
: You continue like that. If you do a perfect search and go to the exact middle always, you will see no more than 10 pages before you find the name.
:
: Greets,
: Eric Goldstein
: http://www.gvh-maatwerk.nl
:
:
:

OK, I think as you said I was confused about the search-algorithm and array or other insertion method.

So then size 6 (for example) for the one-dimentional array simply is,

array[0][1][2][3][4][5]

Then the size 6 for the two dimentional array should simply,

array[0][0], [0][1], [1][0], [1][1], [2][0], [2][1]

or something similer...

and to search either the array in binary way is not the big difference in fact I think the same.

Thanks for the advices!!

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic