Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Sequential Search / Linear Search

tokoGtokoG Posts: 209Member
Hi another question regarding the searches. (As I am studying this topic now)

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??
«1

Comments

  • tsagldtsagld Posts: 621Member
    : Hi another question regarding the searches. (As I am studying this topic now)
    :
    : 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


  • tokoGtokoG Posts: 209Member
    :
    : 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]
  • tsagldtsagld Posts: 621Member
    : :
    : : 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++)
    {
    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!
    }
    }
    }
    }
    }
    [/code]

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


  • LundinLundin Posts: 3,711Member
    : : :
    : : : 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++)
    : {
    : 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!
    : }
    : }
    : }
    : }
    : }
    : [/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.
  • tsagldtsagld Posts: 621Member
    : : : :
    : : : : 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++)
    : : {
    : : 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!
    : : }
    : : }
    : : }
    : : }
    : : }
    : : [/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


  • LundinLundin Posts: 3,711Member
    : : : : :
    : : : : : 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++)
    : : : {
    : : : 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!
    : : : }
    : : : }
    : : : }
    : : : }
    : : : }
    : : : [/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)
  • tokoGtokoG Posts: 209Member
    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?




    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]


  • tsagldtsagld Posts: 621Member
    [b][red]This message was edited by tsagld at 2006-6-28 5:36:0[/red][/b][hr]
    : 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




  • tokoGtokoG Posts: 209Member
    :
    : 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..?
  • tsagldtsagld Posts: 621Member
    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


«1
Sign In or Register to comment.