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 2^N    > # of elements

•          30 element array takes at most 5 steps

2⁵   >  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