Friday 31 July 2015

Arrays in C++ Part 4: Searching Arrays and 2-D Arrays

As we have done a few lessons in arrays (parts one, two and three), let us learn how to find results in large arrays as well as look at 2-D arrays.

Searching Arrays

          Search array for a key value
          Linear search
        Compare each element of array with key value
          Start at one end, go to other
        Useful for small and unsorted arrays
          Inefficient
          If search key not present, examines every element




          Binary search
        Only used with sorted arrays
        Compare middle element with key
          If equal, match found
          If key < middle
        Repeat search on first half of array
          If key > middle
        Repeat search on last half
        Very fast
          At most N steps, where 2N    > # of elements
          30 element array takes at most 5 steps
25   >  30






Multiple Sub-scripted Arrays

          Multiple subscripts
        a[ i ][ j ]
        Tables with rows and columns
        Specify row, then column
        “Array of arrays”
          a[0] is an array of 4 elements
          a[0][0] is the first element of that array



          To initialize
        Default of 0
        Initializers grouped by row in braces
                             int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } };

  
                             int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } };


          Referenced like normal
               cout << b[ 0 ][ 1 ];

        Outputs 0
        Should not be referenced using commas
                             cout << b[ 0, 1 ]; is interpreted as cout << b[1]

          Function prototypes
        Must specify sizes of subscripts
          First subscript not necessary, as with single-scripted arrays
        void printArray( int [][ 3 ] );



          Next: program showing initialization
        After, program to keep track of students grades
        Multiple-subscripted array (table)
        Rows are students
        Columns are grades








About the Author

Unknown

Editorial Team

Post a Comment

 
Codexify © 2015 - Designed by Templateism.com