8: Arrays

What We Will Cover

Continuations

Midterm Questions

Questions from last class?

Homework Questions?

  • Nothing

^ top

8.1: Arrays and Loops

Objectives

At the end of the lesson the student will be able to:

  • Use loops to process array elements
  • Calculate statistics on lists of data stored in arrays

^ top

8.1.1: Processing Array Values in a Loop

  • Array processing is easily done in a loop
  • A for loop is commonly used to process array elements
  • For example, we can use a loop to display the contents of an array
    • int scores[] = {90, 95, 87, 89, 98};
for (int i = 0; i < 5; i++) {
    cout << scores[i] << endl;
}
  • Note the use of the constant length in the array loop

Initializing an Array

  • Similarly, we can initialize array elements to a known value:
    • const int NUMBER_OF_STUDENTS = 5;
int scores[NUMBER_OF_STUDENTS];
for (int i = 0; i < NUMBER_OF_STUDENTS; i++) {
    scores[i] = 100;
    cout << i << ": " << scores[i] << endl;
}

^ top

8.1.2: Initializing From the Keyboard

  • We can also use a loop to initialize values from the keyboard
    • const int NUMBER_OF_STUDENTS = 5;
int score[NUMBER_OF_STUDENTS];
cout << "Enter the score for each of the "
     << NUMBER_OF_STUDENTS << " students:\n";
for (int i = 0; i < NUMBER_OF_STUDENTS; i++) {
    cin >> score[i];
}
  • Note that the loop counter and array index counts from 0 to size - 1

Partially Filled Arrays

  • Note that until the above example finishes, only part of the array is filled
  • This is known as a partially-filled array
  • There is no automatic way to know how many values have been set in an array
  • Instead, the programmer must keep track of which values are entered
  • As shown above, this tracking is done using the index of the array

^ top

8.1.3: Calculating Statistics on an Array of Values

  • Since we can use a loop to access every item in an array, we can sum the array values
  • For example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    int data[] = {1, 2, 3, 4, 5};
    int sum = 0;
    for (int i = 0; i < NUMBER_ITEMS; i++) {
        sum = sum + data[i];
        cout << data[i] << ", ";
    }
    cout << "\nsum = " << sum << endl;
}
  • What code would we add to show the average of the array values?
  • What would we change to find the maximum array value?
  • How would we find the minimum array value?
  • What is the easiest way to initialize minimum and maximum values?

^ top

8.1.4: Copying an Array

  • Sometimes you need to copy the values in one array to another array
  • This is easy to accomplish with a loop

Example of Copying an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    double prices1[] = {0.99, 1.99, 2.99, 3.99, 4.99};
    double prices2[5];

    for (int i = 0; i < NUMBER_ITEMS; i++) {
        prices2[i] = prices1[i];
    }


    for (int i = 0; i < 5; i++) {
        cout << i << ": " << prices1[i] << " = "
             << prices2[i] << endl;
    }
}

^ top

8.1.5: Array Index Out of Range

  • A common error is to access an element outside the range of the array
  • For example, index values for int values[5] are the values 0 through 4
  • What if we tried to access array element 5?
  • Using an out of range index value does not produce an error message!
  • We can see this in the following example
  • Executing these statements usually does not seem to cause a problem
  • However, undetected problems like these may cause many different problems after the code is shipped
  • C++ code is infamous for these types of bugs

Example of Writing Values Beyond the Range of an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<iostream>
using namespace std;

const int SIZE = 3;
const int NUM_VALUES = 5;

int main(void) {
    int values[SIZE];

    cout << "I will store " << NUM_VALUES << " numbers in a "
         << SIZE << "-element array!\n";
    for (int i = 0; i < NUM_VALUES; i++) {
        values[i] = i + 1;
    }

    cout << "If you see this, the computer did not crash!\n";
    for (int i = 0; i < NUM_VALUES; i++) {
        cout << values[i] << endl;
    }
}

^ top

8.1.6: Summary

  • You can use loops to access every array element
  • For example, to assign values to an array and to display array values:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<iostream>
using namespace std;

const int NUMBER_OF_STUDENTS = 5;

int main(void) {
    int score[NUMBER_OF_STUDENTS];

    cout << "Enter the score for each of the "
         << NUMBER_OF_STUDENTS << " students:\n";
    for (int i = 0; i < NUMBER_OF_STUDENTS; i++) {
        cout << "Student #" << i << ": ";
        cin >> score[i];
    }

    cout <<"You entered:" ;
    for (int i = 0; i < NUMBER_OF_STUDENTS; i++) {
        cout << score[i] << endl;
    }
}
  • Another use for loops is to sum the values of an array
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    int data[] = {1, 2, 3, 4, 5};
    int sum = 0;
    for (int i = 0; i < NUMBER_ITEMS; i++) {
        sum = sum + data[i];
        cout << data[i] << ", ";
    }
    cout << "\nsum = " << sum << endl;
}
  • You can also use loops to compute an average, find a minimum or a maximum
  • Loops also allow you to copy all the values from one array and save them in another array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    double prices1[] = {0.99, 1.99, 2.99, 3.99, 4.99};
    double prices2[5];

    for (int i = 0; i < NUMBER_ITEMS; i++) {
        prices2[i] = prices1[i];
    }


    for (int i = 0; i < 5; i++) {
        cout << i << ": " << prices1[i] << " = "
             << prices2[i] << endl;
    }
}
  • The programmer must be very careful to keep the array index within bounds
  • Accessing an array element outside the bounds of an array can cause many problems
    • However, there is no warning by the compiler
  • This is a large source of bugs in C++

^ top

Exercise 8.1

In this exercise we explore using a loop to access every array element.

Specifications

  1. Save the following code file as arrayminimum.cpp.
  2. Add code to find and display the minimum value of the data in the array.
  3. Submit your source-code file as the answer to this exercise.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    int data[] = {1, 2, 3, 4, 5};
    int sum = 0;
    for (int i = 0; i < NUMBER_ITEMS; i++) {
        sum = sum + data[i];
        cout << data[i] << ", ";
    }
    cout << "\nsum = " << sum << endl;
}

^ top

8.2: Arrays and Functions

Objectives

At the end of the lesson the student will be able to:

  • Pass arrays elements as arguments
  • Pass entire arrays as arguments
  • Use arrays in functions
  • Change array elements in functions

^ top

8.2.1: Array Elements as Arguments

  • Indexed variables can be arguments to functions
  • For example, if a program contains these declarations:
    • int i, n, a[10];
void myFunction(int n);
  • You can use indexed variables a[0] through a[9] as arguments
    • myFunction(a[0]);
myFunction(a[3]);
myFunction(a[i]);

For Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 3;

/**
 * Displays a double to the screen
 */
void showPrice(double value);

int main() {
    double data[] = {12.3, 23.45, 3.456};
    for (int  i = 0; i < NUMBER_ITEMS; i++) {
        showPrice(data[i]);
    }
}

void showPrice(double value) {
    cout.setf(ios::fixed);     // fixed, not scientific
    cout.setf(ios::showpoint); // show decimal point
    cout.precision(2);         // show 2 decimal places
    cout << '$' << value << endl;
}

^ top

8.2.2: Arrays as Function Parameters

  • Can use an entire array as an argument to a function
  • When calling the array, use just the array name and no brackets
    • showArray(scores, NUMBER_OF_STUDENTS);
  • To pass an array, the function must have an array parameter
  • You declare an array parameter using empty brackets in the parameter list
    • void showArray(int values[], int size);
  • Following example shows an array used in a function:
    • void showArray(int values[], int size) {
    for (int i = 0; i < size; i++) {
        cout << values[i] << " ";
    }
}
  • Note the use of the size variable
  • You do not know the size of the array that will be passed
  • Size of the array passed can be different for each call
  • So need to pass a size variable to the function
  • You could easily overload the showArray function for different array types

^ top

8.2.3: Changing Array Elements in Functions

  • Array parameters behave much like call-by-reference parameters
    • The function has access to and can change the original array
  • The values of the indexed variables can be changed by the function
  • You can even collect input in a function for an array

For Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 3;

// Fills an array with int values from the keyboard
void fillUp(int a[], int size);

// Displays an array to the screen
void showArray(int a[], int size);

int main() {
    int data[NUMBER_ITEMS];
    fillUp(data, NUMBER_ITEMS);
    showArray(data, NUMBER_ITEMS);
}

void fillUp(int data[], int length) {
    cout << "Enter " << length << " numbers:\n";
    for (int i = 0; i < length; i++) {
        cin >> data[i];
    }
}

void showArray(int values[], int size) {
    cout << "You entered " << size << " numbers:\n";
    for (int i = 0; i < size; i++) {
        cout << values[i] << endl;
    }
}

Using the const Modifier

  • Normally, a function can change the values of array elements
  • You can prevent the modification using the const modifier
    • void showArray(const int values[], int size);
  • The compiler will issue error messages if you accidentally change an array element
  • For example, if you used const and made a mistake in showArray:
    • void showArray(const int values[], int size) {
    for (int i = 0; i < size; i++) {
        values[i]++;  // error
        cout << values[i] << endl;
    }
}
  • Using const, the compiler gives us a message like:
fillup.cpp: In function `void showArray(const int*, int)':
fillup.cpp:27: increment of read-only location
  • If a function with a constant array parameter calls another function using the const array parameter as an argument...
    • The called function must use a const array parameter as well
    • Otherwise, the compiler will issue an error

^ top

8.2.4: Returning an Array

  • Recall that functions can return a value of type int, double, char, or even a class type like string
  • However, functions cannot return arrays
  • Later, we learn how to return a pointer to an array
  • Returning a pointer accomplishes much of the same thing

^ top

8.2.5: Summary

  • Indexed variables can be arguments to functions
  • You can also pass an entire array as an argument to a function
  • To pass an array, the function must have an array parameter
    • void showArray(int a[], int size);
  • Important to pass the size of the array as well
  • Array parameters behave much like call-by-reference parameters
  • The function has access to and can change the original array
  • You can prevent the modification using the const modifier
    • void showArray(const int a[], int size);
  • Functions cannot return arrays

^ top

Exercise 8.2

In this exercise we explore passing an array to a function.

Specifications

  1. Save the following code file as onemore.cpp.
  2. Write a definition for the function addOne() that has a parameter for an int[] and adds one to each element of the array.
  3. Submit your source-code file as the answer to this exercise.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
using namespace std;

// Use this function declaration
void addOne(int data[], int size);

void showArray(int values[], int size);

int main() {
    const int SIZE = 5;
    int data[SIZE] = { 1, 2, 3, 4, 5 };

    showArray(data, SIZE);
    addOne(data, SIZE);
    showArray(data, SIZE);

    return 0;
}

void showArray(int values[], int size) {
    cout << "You entered " << size << " numbers:\n";
    for (int i = 0; i < size; i++) {
        cout << values[i] << endl;
    }
}

// Write function definition here

^ top

8.3: Array Programming Techniques

Objectives

At the end of the lesson the student will be able to:

  • Use partially-filled arrays to solve the fixed-array-size problem
  • Test array equality
  • Search an array
  • Sort an array
  • Understand when to use binary search

^ top

8.3.1: Determining Array Size

  • You often do not know how large to make an array
  • For instance when you use arrays interactively
  • You do not know how large to make the array until the user tells you
  • A common solution to this size problem is to:
    1. Declare the array size to be the largest that could ever be needed
    2. Use code that can deal with partially-filled arrays
  • Consider the following example that takes a list of scores and computes how far any score differs from the average

For Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

/**
 * Shows the difference between each of a list of
 * scores and their average.
 */
#include <iostream>
using namespace std;

const int MAX_NUMBER_SCORES = 10;

/**
 * Partially fills an array and returns the number
 * of elements used.
 */
void fillArray(int a[], int size, int& numberUsed);

/**
 * Returns the average of numbers a[0] through
 * a[numberUsed - 1]
 */
double computeAverage(const int a[], int numberUsed);

/**
 * Displays how much each of the first numberUsed
 * elements differ from their average
 */
void showDifference(const int a[], int numberUsed);

int main(void) {
    int score[MAX_NUMBER_SCORES], numberUsed;

    cout << "This program reads scores and shows how\n"
         << "much each differs from the average.\n";

    fillArray(score, MAX_NUMBER_SCORES, numberUsed);
    showDifference(score, numberUsed);

    return 0;
}

void fillArray(int a[], int size, int& numberUsed) {
    cout << "Enter up to " << size
         << " nonnegative whole numbers.\n"
         << "Enter a negative number when finished.\n\n";

    int next = 0, index = 0;
    while ((next >= 0) && (index < size)) {
        cout << "Enter score #" << (index + 1) << " : ";
        cin >> next;
        if (next > 0) {
            a[index] = next;
            index++;
        }
    }

    numberUsed = index; // return numberUsed
}

void showDifference(const int a[], int numberUsed) {
    double average = computeAverage(a, numberUsed);
    cout << "Average of the " << numberUsed
         << " scores = " << average << endl
         << "The scores are:\n";
    for (int index = 0; index < numberUsed; index++) {
        cout << a[index] << " differs from average by "
             << (a[index] - average) << endl;
    }
}

double computeAverage(const int a[], int numberUsed) {
    double total = 0;
    for (int index = 0; index < numberUsed; index++) {
        total = total + a[index];
    }
    if (numberUsed > 0) {
        return (total / numberUsed);
    } else {
        cout << "ERROR: number of elements is 0.\n"
             << "computeAverage returns 0.\n";
        return 0;
    }
}

Notes About Array-Size Parameters

  • Function fillUp needs to know the array size
  • Other functions only need to know how many elements to use
  • Note that when function fill_array is called, MAX_NUMBER_SCORES is an argument
  • Why not use MAX_NUMBER_SCORES directly without passing it as an argument?
    • Using MAX_NUMBER_SCORES as an argument makes it clear that fillArray requires the array's declared size
    • This makes fillArray easier to use in other programs

^ top

8.3.2: Testing Array Equality

  • Sometimes you have two arrays and you want to compare whether or not they are the same
    • int a[] = {1, 2, 3};
int b[] = {1, 2, 3};
  • You may be tempted to use == to test for equality
    • if (a == b) {
    // do something
}
  • However, this may have unexpected results

For Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
using namespace std;

int main() {
    int a[] = {1, 2, 3};
    int b[] = {1, 2, 3};
    if (a == b) {
        cout << "a == b\n";
    } else {
        cout << "a != b\n";
    }

    return 0;
}
  • Remember that arrays store values in sequential memory locations
  • Thus, different arrays store values in different memory locations
  • Tests using == checks if the base memory addresses are the same
    • if (a == b)
  • Tests if both arrays have the same memory address

Testing Array Elements for Equality

  • To test array elements for equality, you need to check each element
  • Define an equals function that returns true if and only if all the array elements are equal
  • Arrays must also be the same size
  • Updating our previous code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
using namespace std;

const int NUM_ELEMENTS = 3;

bool equals(int a[], int b[], int length);

int main() {
    int a[] = {1, 2, 3};
    int b[] = {1, 2, 3};
    if (a == b) {
        cout << "a == b\n";
    } else {
        cout << "a != b\n";
    }
    if (equals(a, b, NUM_ELEMENTS) == true) {
        cout << "a equals b\n";
    } else {
        cout << "a not equal to b\n";
    }

    return 0;
}

bool equals(int a[], int b[], int length) {
    for (int i = 0; i < length; i++) {
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

^ top

8.3.3: Sequentially Searching an Array

  • Sometimes you want to find out if a particular value exists in an array
  • This is known as searching an array
  • An easy and straightforward algorithm is sequential search
  • In sequential search you:
    • Start at the beginning of the array
    • Compare each value in the array until:
      • If the value is found, then return found
      • If you reach the end of the array, return not found
  • The following example demonstrates sequential search

Example of Sequential Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include<iostream>
using namespace std;

int search(const int array[], int size, int valueToFind);

void showArray(const int values[], int size);

int main(void) {
    const int SIZE = 7;
    int data[] = {-12, -4, 7, 10, 14, 21, 29};
    int valueToFind = 1;

    cout << "For the array:\n";
    showArray(data, SIZE);

    cout << "Enter the value to find (0 to exit): ";
    cin >> valueToFind;
    while (valueToFind != 0) {
        int index = search(data, SIZE, valueToFind);

        if (index > 0) {
            cout << "and found " << data[index] << endl;
        } else {
            cout << "but did not find " << valueToFind
                 << endl;
        }

        cout << "Enter the value to find (0 to exit): ";
        cin >> valueToFind;
    }
}

int search(const int array[], int size, int valueToFind) {
    int index = -1;
    int i = 0;
    for (i = 0; (index == -1) && (i < size); i++) {
        if (valueToFind == array[i]) {
            index = i;
        }
    }
    cout << "Completed search after looking at "
         << i << " array elements\n";
    return index;
}

void showArray(const int values[], int size) {
    for (int i = 0; i < size; i++) {
        cout << values[i] << " ";
    }
    cout << endl;
}
  • On average, would it be any faster to start searching at the end of an array?
  • If an array is sorted, then we can program faster methods -- binary search

^ top

8.3.4: Sorting an Array

  • Sorting is a common task for computers, for example:
    • Sort numbers in ascending order
    • Sort numbers in descending order
    • Sort strings in alphabetic order
  • Many different algorithms for sorting, including:
    • Bubble sort - move item up until in right place
    • Insertion sort - add elements to list one at a time
    • Selection sort - pick 1st, then 2nd, etc.
    • Quick sort - divide and conquer

Selection Sort

  • Selection sort is one of the easiest -- but not the most efficient
  • General algorithm:
    1. Find the smallest element
    2. Swap with the first element
    3. Find the smallest element in the rest of the list
    4. Swap with the first element of the rest of the list
    5. Repeat until the list is sorted

    Pass a[0] a[1] a[2] a[3] a[4] a[5] a[6]
    Original 10 7 29 14 -4 -12 21
    First -12 7 29 14 -4 10 21
    Second -12 -4 29 14 7 10 21
    Third -12 -4 7 14 29 10 21
    Fourth -12 -4 7 10 29 14 21
    Fifth -12 -4 7 10 14 29 21
    Sixth -12 -4 7 10 14 21 29

  • How many passes were needed for a seven element array?

Selection Sort Code

  • Following is selection sort code
  • Have added some statements to show action for each pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <iostream>
using namespace std;

const int NUMBER_ITEMS = 7;

/**
 * Sorts the array so that
 * a[0] <= a[1] <= ... <= a[numberUsed - 1]
 */
void sort(int data[], int numberUsed);

/**
 *Interchanges the values of variable1 and variable2.
 */
void swapValues(int& variable1, int& variable2);

/**
 * Returns the index i such that data[i] is the
 * smallest value between data[start] and data[end].
 */
int findMin(const int data[], int start, int end);

/**
 * Displays an array to the screen
 */
void showArray(int a[], int length);

int main() {
    int a[] = {10, 7, 29, 14, -4, -12, 21};

    cout << "Original: ";
    showArray(a, NUMBER_ITEMS);
    sort(a, NUMBER_ITEMS);
    cout << "\nSorted array:   ";
    showArray(a, NUMBER_ITEMS);
    cout << endl;

    return 0;
}

void sort(int data[], int size) {
    int indexOfMin;
    //Place the correct value in a[index]:
    for (int index = 0; index < size - 1; index++) {
        indexOfMin =  findMin(data, index, size - 1);
        swapValues(data[index], data[indexOfMin]);
        cout << "Pass#" << index << ": ";
        showArray(data, size);
    }
}

void swapValues(int& variable1, int& variable2) {
    cout << "\nSwapping " << variable1
         << " with " << variable2 << endl;
    int temp = variable1;
    variable1 = variable2;
    variable2 = temp;
}


int findMin(const int data[], int start, int end) {
    int indexOfMin = start;
    for (int i = start + 1; i <= end; i++) {
        if (data[i] < data[indexOfMin]) {
            indexOfMin = i;
        }
    }
    cout << "\nFound minimum of " << data[indexOfMin]
         << " at index: " << indexOfMin;
    return indexOfMin;
}

void showArray(int values[], int length) {
    for (int i = 0; i < length; i++) {
        cout << values[i] << "  ";
    }
}
  • Note that every element in the array must have a value
  • Can the array have duplicate items?
  • Also note that the larger task was broken into smaller tasks using functions
    • Helps to organize program and improve clarity

What About Bubble Sort?

  • Another sorting algorithm that is easy to understand and use
  • General algorithm:
    1. Make length passes through the array
    2. For each pass, compare each array element with the next element
    3. If the current element is larger than the next one, swap them
  • Not an efficient sorting algorithm
  • Sometimes simple algorithms perform poorly
  • Simple algorithms are still useful: easy to program and understand
  • If better performance is needed, replace with a better algorithm
  • More information: Sorting Algorithms

^ top

8.3.5: Binary Search

  • Once an array is sorted, can use binary search to find an item
  • Binary search is much faster than sequential search

Binary Search Algorithm

  • A key value is searched for among the values stored in the array.
  • Two index variables lowIdx and highIdx are used to limit the scope of the search.
  • The search proceeds until the element searched for is found or the scope between lowIdx and highIdx is exhausted.
    • The index middleIdx is computed as (lowIdx + highIdx) / 2.
    • If key = data[middleIdx] the search is successful.
    • If key < data[middleIdx], highIdx is lowered to middleIdx.
    • If key > data[middleIdx], lowIdx is raised to middleIdx.
    • If the scope between lowIdx and highIdx is exhausted, the search is unsuccessful.
  • Visual demonstration: BinarySearch

Binary Search Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
using namespace std;

const int NUMBER_ITEMS = 7;

/**
 * Find the index of key in array a
 * return -1 if key is not found
 */
int binarySearch(int a[], int length, int key);

/**
 * Displays an array to the screen
 */
void showArray(int a[], int length);

int main(void) {
    int a[] = {-12, -4, 7, 10, 14, 21, 29};

    int key = 14;
    cout << "Searching array: ";
    showArray(a, NUMBER_ITEMS);
    int index = binarySearch(a, NUMBER_ITEMS, key);
    cout << "Index of " << key << " = "
         << index << endl;
}

int binarySearch(int a[], int length, int key) {
    int step = 0; // tracing
    int lowIdx = 0;
    int highIdx = length - 1;
    int middleIdx;
    while (lowIdx <= highIdx) {
        step++;
        middleIdx = (lowIdx + highIdx) / 2;
        cout << "Step#" << step
             << " lowIdx=" << lowIdx
             << " highIdx=" << highIdx
             << " middleIdx=" << middleIdx
             << endl; // tracing
        if (a[middleIdx] == key) {
            return middleIdx;        // just right
        } else if (a[middleIdx] < key) {
            lowIdx = middleIdx + 1;  // too small
        } else {
            highIdx = middleIdx - 1; // too big
        }
    }
    return -1; // not found
}

void showArray(int values[], int length) {
    for (int i = 0; i < length; i++) {
        cout << values[i] << "  ";
    }
    cout << endl;
}

How Much Faster is Binary Search?

  • Given the sorted array:

    • a[0] a[1] a[2] a[3] a[4] a[5] a[6]
    -12 -4 7 10 14 21 29

  • How many steps to find the value of 14 using sequential search?
  • How many steps to find the value of 14 using binary search?
  • On average for an array of n elements:
    • Sequential search takes n / 2 steps
    • Binary search takes 2 * log2(n) + 2 steps maximum
  • Translating to some array sizes:

    • Array Size floor(log2(n)) + 1
    1 1
    10 4
    100 7
    1000 10
    10,000 14

  • Binary search quickly becomes worth the effort of its implementation
  • Binary search is one algorithm a programming professional should know!

^ top

8.3.6: Summary

  • You can easily enter values into an array for later processing
  • A "partially filled array" is one in which values are stored in an initial segment of the array
  • You use partially-filled arrays when you do not know how large to make to make the array
  • To compare two arrays, you cannot use == on the whole array
  • Instead, you must loop through both arrays and compare each element
  • You can search arrays sequentially to find a value using a loop
  • Sorting algorithms sort array elements into ascending or descending order
  • If an array is sorted, you can use binary search to speed the search process

Check Yourself

  1. How can you solve the problem of not knowing how large to make an array?
  2. If you want to use only part of an array, how do you keep track of how full it is?
  3. If you compare two arrays containing the same values, why does == return false?
  4. Why is binary search faster than sequential search?
  5. What condition must an array be in before you can use binary search?

^ top

Exercise 8.3

In this exercise we write a short program that stores char values in an array and then processes the values

Specifications

  1. Save the following code as reverse.cpp
  2. Add the code to read in 10 characters from the user and display the characters in reverse order from what the user entered.
  3. Submit your program along with your other exercises for this lesson.
1
2
3
4
5
6
7
8

#include <iostream>
using namespace std;

int main() {
    // Enter code here

    return 0;
}

One possible answer.

^ top

Wrap Up

    Reminders

    Due Next: A7: Counting the Odds (4/12/07)
    Exercise 7 and CodeLab Lesson 7 (4/12/07)
    A8: Tic-Tac-Toe (4/19/07)
    Exercise 8 and CodeLab Lesson 8 (4/19/07)

  • When class is over, please shut down your computer
  • You may complete unfinished exercises at the end of the class or at any time before the next class.

^ top

Home | Blackboard | Announcements | Day Schedule | Eve Schedule
Course info | Help | FAQ's | HowTo's | Links

Last Updated: April 10 2007 @09:45:17