Common Array Challenges

In our journey of how to learn C++ step by step, we have discovered that arrays are powerful storage containers. However, simply storing data is not enough. To build useful applications, you must be able to search through that data, find extreme values, and organize the information.

These lecture notes serve as a comprehensive guide to three common array challenges—Searching, Finding Extremes, and Sorting—plus a look at the highly efficient Binary Search.

Definitions

Challenge 1: Finding a Specific Key (Linear Search)

Linear search is the most basic way to find data. You start at the beginning (index 0) and look at every “box” until you find what you need.

Relatable Daily Life Example: The Lost Keys

Imagine you are looking for a specific key on a large keychain with 20 similar-looking keys. You try the first key, then the second, then the third, and so on. You continue this linear process until the door opens (you find the key) or you run out of keys.

The Solution Logic

1. Pass the array, its size, and the “key” you are looking for into a function.
2. Use a loop to traverse the array from index 0 to size – 1.
3. Compare the current element with the key. If they match, return the index immediately.
4. If the loop finishes and the key was never found, return a special value like -1 to indicate failure.

Code Implementation

#include <iostream>
using namespace std;

// Function to find a key in an array
int findKey(double arr[], int size, double key) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            return i; // Key found, return index
        }
    }
    return -1; // Key not found after checking all elements
}

int main() {
    double values[] = {1.2, 3.4, 5.5, 7.8, 9.0};
    int index = findKey(values, 5, 5.5);

    if (index != -1)
        cout << "Key found at index: " << index << endl;
    else
        cout << "Key not found in the array." << endl;

    return 0;
}

Challenge 2: Finding Maximum and Minimum Values

Finding the “highest score” or “lowest price” is a frequent requirement in programming.

Relatable Daily Life Example: The Tallest Student

If you want to find the tallest student in a classroom, you look at the first student and “assume” they are the tallest for now. Then you look at the next student. If they are taller, you “update” your mental record of who is the tallest. You repeat this for every student in the room.

The Solution Logic

1. Create a variable (e.g., maxVal) and initialize it with the first element of the array (index 0).
2. Start a loop from the second element (index 1).
3. Compare each element with maxVal. If the current element is larger, update maxVal with that new value.
4. After the loop ends, maxVal will hold the largest number in the entire array.

Code Implementation

#include <iostream>
using namespace std;

double findMax(double arr[], int size) {
    double maxVal = arr; // Assume first element is max
    for (int i = 1; i < size; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i]; // Update max if a larger value is found
        }
    }
    return maxVal;
}

int main() {
    double marks[] = {45.5, 88.2, 77.0, 92.4, 60.1};
    cout << "Maximum value is: " << findMax(marks, 5) << endl;
    return 0;
}

Challenge 3: Sorting Data (Bubble Sort)

Sorting organizes your data so it is easier to read and search. Bubble Sort is often the first algorithm students learn because its logic is very visual.

Relatable Daily Life Example: Sorting a Deck of Cards

Imagine a row of cards on a table. You compare the first two. If the one on the left is bigger, you swap them. Then you compare the second and third. You keep doing this until the biggest card “bubbles” up to the very end of the row.

The Solution Logic

1. Use nested loops. The outer loop tracks the number of “passes” through the array.
2. The inner loop compares adjacent elements (arr[j] and arr[j+1]).
3. If the element on the left is greater than the one on the right, swap them.
4. With each pass, the largest remaining element moves to its correct position at the end, so the inner loop can run fewer times in each subsequent pass (size - i - 1).

Code Implementation

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) { // Outer loop for passes
        for (int j = 0; j < size - i - 1; j++) { // Inner loop for comparisons
            if (arr[j] > arr[j + 1]) {
                // Swap logic
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int data[] = {9, 0, 2, 1};
    bubbleSort(data, 4);
    cout << "Sorted array: ";
    for(int i = 0; i < 4; i++) cout << data[i] << " ";
    return 0;
}

Advanced Search: Binary Search

While Linear Search checks every element, Binary Search is much faster but requires the array to be sorted first.

How It Works

1. Find the middle element of the array.
2. If the middle element is your key, you are done!
3. If your key is smaller than the middle, ignore the right half of the array and search only the left half.
4. If your key is larger, search only the right half.
5. Repeat this process, cutting the search area in half each time. This is much faster for large datasets (e.g., searching a phonebook with 1,000,000 names).

Interactive Elements: Try It Yourself!

1. Main challenge: Write a program that asks the user:
   =>Size of an array
   =>Elements of the array
   =>A key value
   Then, your program should:
   =>Print the array in sorted (ascending) form.
   =>Find and print the index of the key in the sorted array using binary search (if key found).
   =>Find and print the min and max values of the array.
2. Reflection Prompt: Why does Bubble Sort need two loops instead of just one? (Hint: Watch what happens to the second-largest number during the first pass).
3. Challenge 1: Modify the findMax code to find the minimum value instead. What symbol do you need to change?.
4. Challenge 2: Dry run the Bubble Sort logic on paper with the array {5, 1, 4, 2}. How many swaps occur in the first pass?.
5. Challenge 3: What happens to a Linear Search if the key appears twice in the array? Which index will the function return?.
6. Logic Test: If you have an array of 1,000,000 items, and your key is the very last item, how many comparisons will Linear Search perform?.

Ready to Level Up?

To see these algorithms visualized with step-by-step memory diagrams and live terminal execution:

• Watch the full videos: Search for Lectures 37, 38, and 39 on our channel.
• Practice: Download the source code for these algorithms and try to sort an array in descending order!.

For more technical details on C++ algorithms, visit the C++ Standard Library Reference.

Happy Coding!