Imagine that you have a box containing 10,000 index cards. Each card contains a student's name. You are asked:

"Find the card belonging to Alex."

How do you do it?

You could start at the first card and check every card until you find Alex. Or perhaps the cards are already arranged alphabetically. In that case, you can do something much smarter.

Searching and sorting are closely connected because the way data is organized can dramatically change how efficiently we can search it.

This is one of the most important ideas in algorithms:

Let's formalize the problem. Suppose we have an array containing n values:

We want to determine whether a particular value x exists.
This sounds simple. But there are many different strategies.
The first question we should ask is: If the data is completely unordered, our options are limited. If the data is sorted, however, we can exploit that structure.

The simplest strategy is to check the elements one at a time.
Start at the beginning. Check the first element. If it isn't what we want, move to the next element. Continue until we find the target or reach the end.

linear_search.py · python COPY

def linear_search(values, target):
        for i in range(len(values)):
            if values[i] == target:
                return i

        return -1

If there are n elements, how many might we need to inspect?
In the worst case, the target is at the very end—or isn't present at all. Therefore:

The good news is that linear search requires no special organization. It works on:

• sorted data
• unsorted data
• arrays
• lists

The bad news is that it may have to inspect almost everything.

Now suppose our data is sorted:

We want to find 31.
Instead of starting at the beginning, let's look at the middle. The middle value is 14.
31 is greater than 14. Therefore, we immediately know something important:
31 cannot be anywhere to the left of 14.
We can throw away half of the data. Now look at the remaining half.

The middle value is 27. 31 is greater. Throw away the left half again.

We find 31.
The key idea is not simply "look in the middle." The key idea is:
Suppose we begin with n elements. After one comparison, approximately remain. After two comparisons, remain. After three, remain. Eventually:

. Solving for k:

Therefore:

This is dramatically better than linear search for large datasets.

Consider one million items. A linear search might require comparisons. A binary search requires approximately: comparisons.
That means roughly twenty questions can distinguish between one million possibilities.
This is why logarithmic algorithms are so powerful.

Binary search sounds strictly better than linear search. But there is a catch.
The data has to be sorted. Sorting costs time. Suppose we have an unsorted dataset. We could:

1. Sort the data.
2. Perform binary searches.

If we only need to search once, sorting may not be worth it. But if we are going to search thousands or millions of times, sorting can be an excellent investment.
This gives us an important algorithmic tradeoff:

Sorting means arranging elements according to some ordering rule. For example:

We could sort:

• numbers from smallest to largest
• names alphabetically
• files by size
• products by price
• students by score
• events by time

Sorting is useful because ordered data is often easier to search, analyze, display, and process.
There are many sorting algorithms. The interesting question is:

Imagine sorting a hand of cards. Find the smallest card. Put it first. Then find the next smallest card. Put it second. Continue.

This is essentially selection sort.

selection_sort.py · python COPY

def selection_sort(values):
        n = len(values)

        for i in range(n):
            smallest = i

            for j in range(i + 1, n):
                if values[j] < values[smallest]:
                    smallest = j

            values[i], values[smallest] = values[smallest], values[i]

At position 0, we find the smallest element. At position 1, we find the smallest remaining element. And so on.
How much work does this require? Approximately:

This sum grows proportional to . Therefore,

Quiz // Question 1 OF 1

VIEW ALL SCORE: 0

Insertion sort works differently. Instead of repeatedly finding the smallest element, we maintain a sorted section of the array. Consider:

The first element is already sorted. Take 7. It belongs after 3. Now the first two elements are sorted. Take 9. It belongs after 7. Now:

Take 2. Move larger elements out of the way and insert 2 at the beginning.
The algorithm is similar to sorting a hand of playing cards.

insertion_sort.py · python COPY

def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1

        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1

        values[j + 1] = current

Insertion sort has a worst-case complexity of . So why would anyone use it? Because the worst case isn't the whole story.
Suppose the data is already sorted:

Insertion sort has very little work to do. Its best-case complexity is .
This is an important lesson:

Bubble sort repeatedly compares neighboring elements. If they are in the wrong order, swap them. For example:

Compare 5 and 2. Swap them:

Compare 5 and 8. No swap. Compare 8 and 1. Swap:

After one pass, the largest element has "bubbled" toward the end.
Bubble sort is easy to understand, but its typical complexity is
So why teach it?

We have now seen three simple sorting algorithms.

Algorithm	Basic idea	Typical complexity
Selection sort	Find the smallest remaining element
Insertion sort	Insert each element into sorted section
Bubble sort	Swap neighboring elements

If all three are , does that mean they are basically identical? No. Their actual performance can differ because of:

• how many comparisons they make
• how many elements they move
• how much memory they use
• whether the data is already partially sorted
• whether the algorithm preserves equal elements

Big-O is extremely useful. But it is not the entire story.

Our simple sorting algorithms are generally . Can we do better?
Yes. One of the most important ideas in computer science is called Divide and conquer. Instead of trying to solve one large problem directly:

1. Divide the problem into smaller problems.
2. Solve the smaller problems.
3. Combine the results.

This idea leads us to merge sort.

Suppose we want to sort:

First, divide it:

Divide again:

Continue until the pieces contain one element. A one-element list is already sorted.
Now comes the clever part. We merge the sorted pieces together.

becomes:

And eventually the entire list becomes sorted. At each level, merge sort processes all n elements. The number of levels is approximately . Therefore:

Compare that with .
For large datasets, this difference is enormous.

Quicksort also uses divide and conquer. Instead of splitting the array into equal-sized pieces automatically, we choose a pivot. For example:

Suppose we choose 5 as the pivot. We divide the values into:
values less than 5:

values greater than 5:

Now recursively sort those groups.
The quality of the pivot matters.

Suppose the array is already sorted:

If we repeatedly choose the first element as the pivot, we get extremely unbalanced partitions. Instead of dividing the problem roughly in half, we get:

Then:

And so on. In the worst case, quicksort becomes:

But with good pivot choices, its typical performance is:

We now have several algorithms:

Algorithm	Typical / worst behavior	Main idea
Selection sort		Repeatedly select minimum
Insertion sort	worst case	Insert into sorted section
Bubble sort		Swap neighboring elements
Merge sort		Divide and merge
Quicksort	typical	Partition around pivot

Notice that there is no single "best" sorting algorithm for every situation.

Let's return to our original question.
How do I find something efficiently?
If the data is unsorted, linear search may be necessary.
If the data is sorted, binary search becomes possible.
But sorting the data with an efficient algorithm costs
So we might have:

This is an extremely common pattern in real software.

When faced with an algorithmic problem, don't immediately ask:
"Which algorithm do I remember?"
Instead ask:

1. What operations do I need to perform?
2. How much data do I have?
3. Is the data already organized?
4. How often will I perform the operation?
5. Do I care about worst-case performance?
6. How much memory can I use?

There is not necessarily one correct answer. The goal is to justify your design decisions.

Quiz // Question 1 OF 5

VIEW ALL SCORE: 0

Suppose someone tells you:
"I have a million numbers. I need to find one of them."

Before choosing an algorithm, what questions would you ask?
The important skill is not knowing that binary search exists.
The important skill is knowing when binary search is appropriate.
And that is the larger lesson of algorithms: