Finding Min, Max, and Searching

Real-world analogy

What is it?

Finding min, max, and searching are fundamental array operations. Min/max find the extreme values by scanning through all elements and tracking the best seen so far. Linear search checks each element until a match is found.

Real-world relevance

Your phone's weather app finds the week's highest and lowest temperatures using min/max. When you search for a contact by name, your phone does a search through a list. When a game shows 'High Score,' it found the maximum of all stored scores. These operations are everywhere!

Key points

• Finding the Maximum — To find the largest value in an array, start by assuming the first element is the maximum: maxVal = arr[0]. Then loop through the rest and whenever you find something bigger, update maxVal. After the loop, maxVal holds the biggest value. This is called the 'running maximum' technique.
• Finding the Minimum — Finding the minimum is the exact same pattern as maximum, but you check for smaller values instead. Start with minVal = arr[0], then loop and update whenever arr[i] .
• Finding the Position (Index) of Min/Max — Sometimes the problem asks 'where' the maximum is, not 'what' it is. To track the position, keep a variable like maxIdx = 0, and whenever you update the max value, also update maxIdx = i. This tells you which box in the array holds the biggest value.
• Linear Search — Linear search means checking every element one by one to find a target value. Loop through the array and if arr[i] == target, you found it! This takes O(n) time. For unsorted arrays, linear search is your only option. For sorted arrays, binary search is faster (we will learn that later).
• Counting Occurrences — To count how many times a value appears, combine linear search with counting. Loop through the array and increment a counter whenever arr[i] == target. This is a very common CP pattern — many problems ask you to count how many elements equal a specific value.
• Using Built-in Functions — C++ has built-in functions that make life easier. *min_element(arr, arr+n) finds the minimum, *max_element(arr, arr+n) finds the maximum. The count() function from counts occurrences. But in CP, knowing how to write these yourself is important for customization!
• Second Largest Element — A classic CP problem: find the second largest. One way: find the max first, then find the max again ignoring the first max. A better way: track both first and second as you scan. If arr[i] > first, second becomes first and first becomes arr[i]. If arr[i] > second and arr[i] != first, update second.

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // Find maximum and its position
    int maxVal = arr[0], maxIdx = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
            maxIdx = i;
        }
    }
    cout << "Max: " << maxVal << " at index " << maxIdx << endl;
    
    // Find minimum
    int minVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < minVal) {
            minVal = arr[i];
        }
    }
    cout << "Min: " << minVal << endl;
    
    // Search for a value
    int target;
    cin >> target;
    int foundIdx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            foundIdx = i;
            break;  // Found it, stop searching!
        }
    }
    
    if (foundIdx != -1) {
        cout << target << " found at index " << foundIdx << endl;
    } else {
        cout << target << " not found!" << endl;
    }
    
    return 0;
}
// Input:  5
//         3 7 1 9 4
//         7
// Output: Max: 9 at index 3
//         Min: 1
//         7 found at index 1

Line-by-line walkthrough

1. 1. We read the array using our standard input pattern.
2. 2. For maximum: we assume arr[0] is the max, then check every other element starting from index 1.
3. 3. If arr[i] > maxVal, we update both maxVal and maxIdx to remember the new champion.
4. 4. Finding minimum is the same but we check arr[i] < minVal instead.
5. 5. For search: we set foundIdx = -1 (meaning 'not found yet').
6. 6. We loop and check each element. When we find the target, we save the index and break.
7. 7. After the loop, if foundIdx is still -1, the target was not in the array.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    cout << "Max: " << maxVal << endl;
    
    return 0;
}
// Input: 4
//        -5 -3 -8 -1
// Expected: Max: -1
// Actual Output: Max: 0

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Min, Max, and Linear Search in C++ (Abdul Bari)
• Searching Algorithms — GeeksforGeeks (GeeksforGeeks)
• Easy Searching Problems (Codeforces)