Skip to content

Beginner · Functions and arrays · topic 15 of 60 · 30 min

2D arrays and classic array algorithms

Explanation

A 2D array like int seats[10][20] is a grid of rows and columns stored row after row in memory (row-major order). When passing one to a function, every dimension except the first must be given: void show(int g[][20], int rows). Classic algorithms on arrays include linear and binary search, finding the min and max, reversing in place, and simple sorts like bubble and selection sort.

2D arrays

c
int marks[3][4] = {
    {78, 82, 91, 66},     /* student 0: four subjects */
    {65, 70, 58, 74},     /* student 1 */
    {88, 95, 84, 90},     /* student 2 */
};
printf("%d\n", marks[2][1]);   /* 95: row 2, column 1 */

for (int s = 0; s < 3; s++) {
    int total = 0;
    for (int sub = 0; sub < 4; sub++) total += marks[s][sub];
    printf("Student %d: %d\n", s, total);
}

Row-major layout

output
int g[2][3] = {{1, 2, 3}, {4, 5, 6}};
memory: | 1 | 2 | 3 | 4 | 5 | 6 |
         g[0][0..2]  g[1][0..2]
address of g[r][c] = start + (r * 3 + c) * sizeof(int)
Looping row by row (outer loop over rows) reads memory in order, which is faster because of CPU caches.

Because the compiler needs the row length to compute addresses, a function parameter must state every dimension except the first: void print_grid(int g[][3], int rows). C99 also allows variable-length array parameters: void print_grid(int rows, int cols, int g[rows][cols]).

Searching

c
int linear_search(const int a[], int n, int target) {      /* any array: up to n steps */
    for (int i = 0; i < n; i++) if (a[i] == target) return i;
    return -1;
}

int binary_search(const int a[], int n, int target) {      /* SORTED array: about log2(n) steps */
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;                         /* avoids overflow of lo + hi */
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

Reverse in place, min and max

c
void reverse(int a[], int n) {
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        int tmp = a[i]; a[i] = a[j]; a[j] = tmp;            /* swap the two ends */
    }
}

Simple sorts

c
void selection_sort(int a[], int n) {     /* find the smallest, put it first, repeat */
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[min]) min = j;
        int tmp = a[i]; a[i] = a[min]; a[min] = tmp;
    }
}

void bubble_sort(int a[], int n) {        /* swap neighbours that are out of order */
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - pass; j++) {
            if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1; }
        }
        if (!swapped) break;              /* already sorted: stop early */
    }
}
Both are O(n²): fine for small arrays and interviews. For real code use qsort from <stdlib.h> (module 9).
Careful: Binary search on unsorted data returns wrong answers silently. And the classic overflow bug, mid = (lo + hi) / 2, breaks when lo + hi exceeds INT_MAX; lo + (hi - lo) / 2 is the safe form.
Think of it like this: Binary search is how you find a name in a printed telephone directory: open near the middle, decide which half the name is in, and ignore the other half. Selection sort is how you might arrange cards in your hand: find the smallest, put it on the left, then repeat with the rest.
Tip: Practise these by hand with 6 numbers on paper before coding. Interviewers often ask you to trace a few passes of bubble sort aloud.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

2D arrays and classic array algorithms · 1/6

2D arrays and algorithms

In this lesson you will use 2D arrays and classic array algorithms.

Prefer a video by a teacher? Find free videos on “c 2d array binary search bubble sort selection sort tutorial” on YouTube ↗

In real life: Finding a free seat block in a bus

A bus-booking kiosk stores seats as a 2D array (rows × 4 seats, 1 = booked). To seat a family of three together, it scans each row for three consecutive free seats.

c
int find_row(int seats[][4], int rows, int need) {
    for (int r = 0; r < rows; r++) {
        int run = 0;
        for (int c = 0; c < 4; c++) {
            run = seats[r][c] ? 0 : run + 1;
            if (run == need) return r;
        }
    }
    return -1;
}

Practice (0/3 done)

Task 1 · Question

int g[2][3] = {{1, 2, 3}, {4, 5, 6}}; What is g[1][2] + g[0][1]?

Task 2 · Code · Javascript

The same selection sort algorithm in JavaScript, which runs here: write selectionSort(a) that sorts the array IN PLACE (do not use .sort) and returns the number of swaps where i !== min.

Task 3 · Practice

Write a C program with a 5 × 4 array of marks (5 students, 4 subjects). Print each student's total, each subject's average, and the student with the highest total. Then copy the totals into a 1D array, sort it with bubble sort (with the early-exit flag), and print the sorted totals.

Quick quiz

Question 1

1.In a function parameter for a 2D int array with 4 columns, which is valid?

Question 2

2.Which must be true for binary search?

Question 3

3.What is the time complexity of bubble sort in the worst case?

Question 4

4.Why is mid = lo + (hi - lo) / 2 preferred over (lo + hi) / 2?

Read more (free)

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

In a function parameter for a 2D int array with 4 columns, which is valid?

Answer: int g[][4]

All dimensions except the first are required.

Which must be true for binary search?

Answer: The array is sorted

It relies on sorted order.

What is the time complexity of bubble sort in the worst case?

Answer: O(n²)

Nested loops over the array.

Why is mid = lo + (hi - lo) / 2 preferred over (lo + hi) / 2?

Answer: It avoids integer overflow for large indexes

lo + hi can exceed INT_MAX.

Why write mid = lo + (hi - lo) / 2?Related

Answer: It avoids int overflow of lo + hi on huge arrays

lo + hi can exceed Integer.MAX_VALUE.

From Two-dimensional arrays and array algorithms

What is the index of the last item in an array of length 8?Related

Answer: 7

Indexes go from 0 to Length - 1.

From Arrays: one name, many values

How many frees does an array of 5 row pointers (each row malloc'd) need?Related

Answer: 6

5 rows + the pointer array.

From Dynamic strings and 2D arrays

Why do C functions that take an array also take its size?Related

Answer: Because a C array passed to a function decays into a pointer and loses its size

Inside the function the array is just a pointer to the first element.

From Arrays, std::array and a first look at std::vector

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Strings are char arrays →

Next steps

  1. This is the last topic of “Functions and arrays”. The module exam comes next.
  2. Module 3 exam: Functions and arrays · 12 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Strings in C. 60 topics left in the course before the final exam.

← Previous: Arrays