It looks like you're new here. If you want to get involved, click one of these buttons!

- 140.8K All Categories
- 103.6K Programming Languages
- 6.5K Assembler Developer
- 1.9K Basic
- 39.9K C and C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.7K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 543 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 315 Console programming
- 90 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 739 Computer Hardware
- 3.4K Database & SQL
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 257 XML Development
- 3.3K Classifieds
- 198 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 602 Jobs Wanted
- 208 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 8 Join the Team
- 354 Comments on this site
- 69 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 624 Off topic board
- 194 Mobile & Wireless
- 66 Android
- 126 Palm Pilot
- 338 Multimedia
- 154 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 26 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 370 MS-DOS
- 0 Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 935 Software Development
- 416 Algorithms
- 68 Object Orientation
- 91 Project Management
- 94 Quality & Testing
- 265 Security
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 3 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 35 JQuery
- 300 WEB Servers
- 148 WEB-Services / SOAP

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

But... [red]how about [b]three-dimentional array of size N?[/b][/red]

The [b]worst[/b] and [b]best[/b]?

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

[b]array[N][N][N][/b]

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

Is that so??

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven

© 1997-2015 Programmersheaven.com - All rights reserved.

## Comments

621:

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

:

: But... [red]how about [b]three-dimentional array of size N?[/b][/red]

: The [b]worst[/b] and [b]best[/b]?

:

: I dont think I've ever learn [b]three dimentional array[/b] but I assume it's like,

:

: [b]array[N][N][N][/b]

:

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

:

: Is that so??

No.

[b]array[N][N][N][/b] 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

209: No.

: [b]array[N][N][N][/b] 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].

:

[blue]

Hi Eric

I am not sure what three dimentional array is.

Is it the.. [b]array[string length][column][row][/b] though?

In that case, if [b]N=2[/b], 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?

[/blue]

621: : No.

: : [b]array[N][N][N][/b] 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].

: :

: [blue]

: Hi Eric

:

: I am not sure what three dimentional array is.

: Is it the.. [b]array[string length][column][row][/b] though?

:

: In that case, if [b]N=2[/b], 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?

:

: [/blue]

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:

[code]

//store temperatures by hour, for one day:

int temperatures[24];

//to get the temperature at noon:

int temp = temperatures[12];

[/code]

Obvious, isn't it?

Now you decide you want to keep track of the temperatures for a whole month:

[code]

//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++

[/code]

Now you decide to keep track of the temperatures for a whole year:

[code]

//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];

[/code]

You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:

[code]

//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];

[/code]

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:

[code]

for (int y=0; y<100; y++)<br />{

for (int m=0; m<12; m++)<br /> {

for (int d=0; d<31; d++)<br /> {

for (int h=0; h<24; h++)<br /> {

if (temperatures[y][m][d][h] > 100)

{

//found!

}

}

}

}

}

[/code]

Greets,

Eric Goldstein

http://www.gvh-maatwerk.nl

3,711: : : No.

: : : [b]array[N][N][N][/b] 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].

: : :

: : [blue]

: : Hi Eric

: :

: : I am not sure what three dimentional array is.

: : Is it the.. [b]array[string length][column][row][/b] though?

: :

: : In that case, if [b]N=2[/b], 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?

: :

: : [/blue]

:

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

: [code]

: //store temperatures by hour, for one day:

: int temperatures[24];

:

: //to get the temperature at noon:

: int temp = temperatures[12];

: [/code]

: Obvious, isn't it?

:

: Now you decide you want to keep track of the temperatures for a whole month:

: [code]

: //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++

: [/code]

:

: Now you decide to keep track of the temperatures for a whole year:

: [code]

: //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];

: [/code]

:

: You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:

: [code]

: //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];

: [/code]

:

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

:

: [code]

: for (int y=0; y<100; y++)<br />: {

: for (int m=0; m<12; m++)<br />: {

: for (int d=0; d<31; d++)<br />: {

: for (int h=0; h<24; h++)<br />: {

: if (temperatures[y][m][d][h] > 100)

: {

: //found!

: }

: }

: }

: }

: }

: [/code]

:

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

621: : : : No.

: : : : [b]array[N][N][N][/b] 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].

: : : :

: : : [blue]

: : : Hi Eric

: : :

: : : I am not sure what three dimentional array is.

: : : Is it the.. [b]array[string length][column][row][/b] though?

: : :

: : : In that case, if [b]N=2[/b], 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?

: : :

: : : [/blue]

: :

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

: : [code]

: : //store temperatures by hour, for one day:

: : int temperatures[24];

: :

: : //to get the temperature at noon:

: : int temp = temperatures[12];

: : [/code]

: : Obvious, isn't it?

: :

: : Now you decide you want to keep track of the temperatures for a whole month:

: : [code]

: : //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++

: : [/code]

: :

: : Now you decide to keep track of the temperatures for a whole year:

: : [code]

: : //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];

: : [/code]

: :

: : You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:

: : [code]

: : //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];

: : [/code]

: :

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

: :

: : [code]

: : for (int y=0; y<100; y++)<br />: : {

: : for (int m=0; m<12; m++)<br />: : {

: : for (int d=0; d<31; d++)<br />: : {

: : for (int h=0; h<24; h++)<br />: : {

: : if (temperatures[y][m][d][h] > 100)

: : {

: : //found!

: : }

: : }

: : }

: : }

: : }

: : [/code]

: :

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

[code]

//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];

[/code]

Greets,

Eric Goldstein

http://www.gvh-maatwerk.nl

3,711: : : : : No.

: : : : : [b]array[N][N][N][/b] 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].

: : : : :

: : : : [blue]

: : : : Hi Eric

: : : :

: : : : I am not sure what three dimentional array is.

: : : : Is it the.. [b]array[string length][column][row][/b] though?

: : : :

: : : : In that case, if [b]N=2[/b], 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?

: : : :

: : : : [/blue]

: : :

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

: : : [code]

: : : //store temperatures by hour, for one day:

: : : int temperatures[24];

: : :

: : : //to get the temperature at noon:

: : : int temp = temperatures[12];

: : : [/code]

: : : Obvious, isn't it?

: : :

: : : Now you decide you want to keep track of the temperatures for a whole month:

: : : [code]

: : : //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++

: : : [/code]

: : :

: : : Now you decide to keep track of the temperatures for a whole year:

: : : [code]

: : : //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];

: : : [/code]

: : :

: : : You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:

: : : [code]

: : : //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];

: : : [/code]

: : :

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

: : :

: : : [code]

: : : for (int y=0; y<100; y++)<br />: : : {

: : : for (int m=0; m<12; m++)<br />: : : {

: : : for (int d=0; d<31; d++)<br />: : : {

: : : for (int h=0; h<24; h++)<br />: : : {

: : : if (temperatures[y][m][d][h] > 100)

: : : {

: : : //found!

: : : }

: : : }

: : : }

: : : }

: : : }

: : : [/code]

: : :

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

: [code]

: //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];

: [/code]

:

:

: 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)

209The best way to picturise two,three, multi dimentional array!!

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

[b][88*12*31*24 + 4*31*24 + [red]22[/red]*24 + [red]16[/red]][/b]

insted?

How about in [b]binary search[/b]?

[b]one-dimentional[/b] array search and [b]two-dimentional[/b] array search. Worst case and the best case.

[blue]

I think the [b]best case[/b] for [b]one-dimentional[/b] is the [b]one time[/b] for both dimentions. Just the [b]root node[/b] happens to be the targeted one.

For [b]worst case[/b], it has to go all the way down to the [b]leaf node[/b] which means I think the [b]one level[/b] of comparison is counted as [b]one time[/b] 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 [red]3[/red]

right of the root node: 4.......................level [red]3[/red]

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

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

[/blue]

[red]But then, what is the [b]TWO-DIMENTIONAL[/b] binary tree???[/red]

621: 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, [red]23rd[/red], 1998, [red]16:00pm[/red], isn't it;

:

: [b][88*12*31*24 + 4*31*24 + [red]22[/red]*24 + [red]16[/red]][/b]

:

: insted?

[green]

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

[/green]

:

:

: How about in [b]binary search[/b]?

: [b]one-dimentional[/b] array search and [b]two-dimentional[/b] array search. Worst case and the best case.

:

: [blue]

: I think the [b]best case[/b] for [b]one-dimentional[/b] is the [b]one time[/b] for both dimentions. Just the [b]root node[/b] happens to be the targeted one.

: For [b]worst case[/b], it has to go all the way down to the [b]leaf node[/b] which means I think the [b]one level[/b] of comparison is counted as [b]one time[/b] 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 [red]3[/red]

: right of the root node: 4.......................level [red]3[/red]

:

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

:

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

: [/blue]

:

: [red]But then, what is the [b]TWO-DIMENTIONAL[/b] binary tree???[/red]

Binary search reduces the search range by 50% on each iteration.

So, start with 12 elements

- 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

209: Binary search reduces the search range by 50% on each iteration.

: So, start with 12 elements

: - 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 [b]two dimentiona array[/b] in the binary search?

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

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

621Don'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