Searching and Sorting: Your First Algorithms

Teach the computer to find things and put them in order

Big Idea: An algorithm is just a clear list of steps that solves a problem. In this topic you meet your very first famous algorithms: ways to search for a value inside an array, and ways to sort an array into order. The best part? You already know every tool you need — arrays, loops, and functions from the earlier lessons.

By the end you will be able to:

run a linear search to find a value one item at a time,
run a binary search on a sorted array by cutting it in half,
sort an array with bubble sort and selection sort,
explain why some of these steps are much faster than others.

1. What is an algorithm?

An algorithm is a set of clear, step-by-step instructions that always finishes and gives an answer. A cooking recipe is an algorithm. The steps for tying your shoes are an algorithm. In programming, we write algorithms as C++ code so the computer can follow them.

Two of the most common jobs a computer does are searching (finding one item among many) and sorting (putting items in order, such as smallest to largest). Think about a library: you can only find a book quickly because the books are already sorted on the shelves. Searching and sorting work together all the time.

All of today's algorithms work on an array of numbers using ordinary for and while loops. Nothing new — just clever ways to arrange the loops you already know.

2. Linear search: check them one by one

Linear search is the simplest way to find something. You start at the first item and walk along, one at a time, until you either find what you want or reach the end. It is exactly what you do when you look for a friend by checking every face in a crowd.

The function below returns the index where it found the target, or -1 if the value is not in the array. We use -1 because no real array position is negative, so it is a safe "not found" signal.

#include <iostream>
using namespace std;

// Returns the index of target, or -1 if it is not in the array.
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;        // found it - stop and report where
        }
    }
    return -1;               // walked the whole array, not here
}

int main() {
    int nums[5] = {4, 8, 15, 16, 23};
    cout << linearSearch(nums, 5, 15) << endl;   // 2
    cout << linearSearch(nums, 5, 99) << endl;   // -1
    return 0;
}

Expected output:

2
-1

Linear search always works, even on a messy, unsorted array. Its downside is speed: if the value is last (or missing), it must check every item.

Searching and Sorting: Your First Algorithms