These are the notes for C Coding Questions, episode 12, placement practice for people who finished the SyntaxPilot C course. Searching questions: linear vs binary search (and the famous (lo + hi) / 2 overflow), the first and last occurrence of a value in a sorted array, and counting occurrences with two binary searches.
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, Linux x86-64, 32-bit int), the SyntaxPilot compiler's C command with warnings on, and every output below is real. The compiler stops a program after 8 seconds (Time Limit Exceeded), like an online judge.
Real-life pictures
| In real life | In C |
|---|---|
| finding a word in a dictionary: open the middle, go left or right | binary search: halve the range every step |
| a result list sorted by marks: the first and the last student with 75 | first and last occurrence |
| how many students got 75? last minus first plus one | count occurrences |
Q1: Search in a sorted array
Problem. Read n sorted integers, then q queries. A query is one value x to look for. For each, print the index of x, or -1 if it isn't there.
| Array | x | Output |
|---|---|---|
2 5 8 12 16 |
12 | 3 |
| 2 | 0 | |
| 16 | 4 | |
| 7 | -1 | |
| (empty) | 5 | -1 |
Edge cases: the first element, the last, a missing value, n = 0, many queries.
The obvious attempt: linear search
Linear search looks at every element from the start. It works on any array, sorted or not.
#include <stdio.h>
int search(int a[], int n, int x) {
for (int i = 0; i < n; i++)
if (a[i] == x) return i;
return -1;
}
int main() {
int n, q, x, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &q);
while (q--) {
scanf("%d", &x);
printf("%d at %d\n", x, search(a, n, x));
}
return 0;
}
Input 5 / 2 5 8 12 16 / 3 / 12 2 7:
12 at 3
2 at 0
7 at -1
The stress test: 200,000 values (0 2 4 …), 200,000 queries, all odd, so all missing:
#include <stdio.h>
int search(int a[], int n, int x) {
for (int i = 0; i < n; i++)
if (a[i] == x) return i;
return -1;
}
int a[200000];
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int i = 0; i < n; i++) a[i] = 2 * i;
int found = 0;
for (int k = 0; k < q; k++)
if (search(a, n, 2 * k + 1) != -1) found++;
printf("found %d of %d\n", found, q);
return 0;
}
Input 200000 200000:
Time Limit Exceeded (stopped after 8 seconds)
A missing value makes linear search read all n values: n × q = 40 billion steps.
The fix: binary search
The array is sorted. Keep a range lo..hi where x could be, and look at the middle a[mid]:
a[mid] == x: found.a[mid] < x: everything up tomidis too small, solo = mid + 1.a[mid] > x: everything frommidon is too big, sohi = mid - 1.lo > hi: the range is empty,xisn't there.
Every step halves the range, so it takes about log₂ n steps: 200,000 → 18 steps; a billion → 30.
2 5 8 12 16, find 12: lo=0 hi=4 mid=2: 8 < 12 -> lo = 3
lo=3 hi=4 mid=3: 12 -> found at 3
find 7: lo=0 hi=4 mid=2: 8 > 7 -> hi = 1
lo=0 hi=1 mid=0: 2 < 7 -> lo = 1
lo=1 hi=1 mid=1: 5 < 7 -> lo = 2 lo > hi -> -1
#include <stdio.h>
int search(int a[], int n, int x) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int main() {
int n, q, x, a[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &q);
while (q--) {
scanf("%d", &x);
printf("%d at %d\n", x, search(a, n, x));
}
return 0;
}
Input 5 / 2 5 8 12 16 / 5 / 12 2 16 7 20:
12 at 3
2 at 0
16 at 4
7 at -1
20 at -1
Input 0 / 1 / 5:
5 at -1
With n = 0, hi starts at -1, the loop never runs, and the answer is -1.
The same stress test:
#include <stdio.h>
int search(int a[], int n, int x) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int a[200000];
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int i = 0; i < n; i++) a[i] = 2 * i;
int found = 0;
for (int k = 0; k < q; k++)
if (search(a, n, 2 * k + 1) != -1) found++;
printf("found %d of %d\n", found, q);
return 0;
}
Input 200000 200000:
found 0 of 200000
Complexity: O(log n) per query, O(1) space. Binary search needs a sorted array; sorting first costs O(n log n), which pays off when there are many queries.
The overflow: (lo + hi) / 2
A guessing game: a secret from 1 to 2,000,000,000; after each guess you learn "higher" or "lower". That's binary search on the range itself (about 31 guesses). Written the textbook way:
#include <stdio.h>
int main() {
int secret;
scanf("%d", &secret);
int lo = 1, hi = 2000000000, steps = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
steps++;
if (mid == secret) {
printf("found %d in %d steps\n", mid, steps);
return 0;
}
if (mid < secret) lo = mid + 1;
else hi = mid - 1;
}
printf("not found after %d steps\n", steps);
return 0;
}
Input 1000:
found 1000 in 29 steps
Input 1999999999:
Time Limit Exceeded (stopped after 8 seconds)
Once lo passes about 1.5 billion, lo + hi is over 3 billion, more than INT_MAX (2,147,483,647). Signed overflow is undefined behaviour: the standard makes no promise at all. In this build mid went wrong and the loop never ended.
The fix: mid = lo + (hi - lo) / 2. It is the same middle, but hi - lo (the size of the range) always fits, and lo plus half of it never passes hi. This exact bug sat for years in the binary search of widely used libraries, because nobody tested arrays with more than a billion elements.
#include <stdio.h>
int main() {
int secret;
scanf("%d", &secret);
int lo = 1, hi = 2000000000, steps = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
steps++;
if (mid == secret) {
printf("found %d in %d steps\n", mid, steps);
return 0;
}
if (mid < secret) lo = mid + 1;
else hi = mid - 1;
}
printf("not found after %d steps\n", steps);
return 0;
}
Input 1999999999:
found 1999999999 in 30 steps
Input 2000000000:
found 2000000000 in 31 steps
Input 1:
found 1 in 30 steps
Input 1000:
found 1000 in 29 steps
Q2: First and last occurrence
Problem. A sorted array where values repeat. For each x, print the index of its first copy and its last copy, or -1 -1.
| Array | x | Output |
|---|---|---|
1 2 2 2 3 |
2 | first 1, last 3 |
| 1 | first 0, last 0 | |
| 4 | first -1, last -1 | |
5 5 5 5 |
5 | first 0, last 3 |
The obvious attempt: the Q1 binary search
Input 5 / 1 2 2 2 3 / 1 / 2:
2 at 2
Index 2, but the first 2 is at index 1. Binary search stops at whichever copy it lands on.
The fix: on a match, remember it and keep going
- first: on a match,
ans = midand keep searching left (hi = mid - 1): an earlier copy may be there. - last: on a match,
ans = midand keep searching right (lo = mid + 1).
The range still halves every step: O(log n).
The main loop uses while (scanf("%d", &x) == 1): scanf returns how many values it read, so the loop stops at the end of the input.
#include <stdio.h>
int first(int a[], int n, int x) {
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) {
ans = mid;
hi = mid - 1;
}
else if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
int last(int a[], int n, int x) {
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) {
ans = mid;
lo = mid + 1;
}
else if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
int main() {
int n, x, a[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (scanf("%d", &x) == 1)
printf("%d: first %d, last %d\n", x, first(a, n, x), last(a, n, x));
return 0;
}
Input 5 / 1 2 2 2 3 / 2 1 3 4:
2: first 1, last 3
1: first 0, last 0
3: first 4, last 4
4: first -1, last -1
Input 4 / 5 5 5 5 / 5:
5: first 0, last 3
Input 0 / 3:
3: first -1, last -1
Input 1 / 9 / 9 8:
9: first 0, last 0
8: first -1, last -1
Complexity: two binary searches, O(log n), O(1) space.
Q3: Count occurrences in a sorted array
Problem. For each x, print how many times it appears in the sorted array.
| Array | x | Output |
|---|---|---|
1 2 2 2 3 |
2 | 3 times |
| 4 | 0 times | |
| 1 | 1 time | |
4 4 4 4 4 4 |
4 | 6 times |
The obvious attempt: find one copy and walk both ways
The stress test: 200,000 values (the first half 7, the second half 9) and 400,000 queries alternating 7 and 9:
#include <stdio.h>
int search(int a[], int n, int x) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int count(int a[], int n, int x) {
int p = search(a, n, x);
if (p == -1) return 0;
int l = p, r = p;
while (l > 0 && a[l - 1] == x) l--;
while (r < n - 1 && a[r + 1] == x) r++;
return r - l + 1;
}
int a[200000];
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int i = 0; i < n; i++) a[i] = (i < n / 2) ? 7 : 9;
long long total = 0;
for (int k = 0; k < q; k++)
total += count(a, n, (k % 2) ? 9 : 7);
printf("total %lld\n", total);
return 0;
}
Input 200000 400000:
Time Limit Exceeded (stopped after 8 seconds)
The walk visits every copy: 100,000 per query × 400,000 queries = 40 billion steps. It is O(n) per query in the worst case.
The fix: last − first + 1
Copies sit together from first(x) to last(x), so count = last - first + 1, or 0 if first is -1. For 2 in 1 2 2 2 3: 3 − 1 + 1 = 3.
#include <stdio.h>
int first(int a[], int n, int x) {
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) {
ans = mid;
hi = mid - 1;
}
else if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
int last(int a[], int n, int x) {
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) {
ans = mid;
lo = mid + 1;
}
else if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
int count(int a[], int n, int x) {
int f = first(a, n, x);
if (f == -1) return 0;
return last(a, n, x) - f + 1;
}
int main() {
int n, x, a[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (scanf("%d", &x) == 1)
printf("%d appears %d times\n", x, count(a, n, x));
return 0;
}
Input 5 / 1 2 2 2 3 / 2 4 1:
2 appears 3 times
4 appears 0 times
1 appears 1 times
Input 6 / 4 4 4 4 4 4 / 4 5:
4 appears 6 times
5 appears 0 times
Input 0 / 1:
1 appears 0 times
The same stress test:
#include <stdio.h>
int first(int a[], int n, int x) {
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) {
ans = mid;
hi = mid - 1;
}
else if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
int last(int a[], int n, int x) {
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) {
ans = mid;
lo = mid + 1;
}
else if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
int count(int a[], int n, int x) {
int f = first(a, n, x);
if (f == -1) return 0;
return last(a, n, x) - f + 1;
}
int a[200000];
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int i = 0; i < n; i++) a[i] = (i < n / 2) ? 7 : 9;
long long total = 0;
for (int k = 0; k < q; k++)
total += count(a, n, (k % 2) ? 9 : 7);
printf("total %lld\n", total);
return 0;
}
Input 200000 400000:
total 40000000000
total is long long because 40 billion doesn't fit an int.
Complexity: O(log n) per query, however many copies there are; O(1) space.
Complexity summary
| Task | Method | Time | Space |
|---|---|---|---|
| search | linear search | O(n) per query (any array) | O(1) |
| binary search | O(log n) per query (sorted only) | O(1) | |
| first / last occurrence | binary search that stops on a match | O(log n), wrong copy | O(1) |
ans = mid, keep searching |
O(log n) | O(1) | |
| count | find + walk | O(n) worst case per query | O(1) |
| last − first + 1 | O(log n) per query | O(1) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| linear search for every query | Time Limit Exceeded |
n × q steps | sort once, binary search |
int mid = (lo + hi) / 2; |
no error: loops forever (UB) for a secret near 2 billion | lo + hi passes INT_MAX |
lo + (hi - lo) / 2 |
return mid; on the first match |
no error: 2 at 2, the first 2 is at 1 |
it finds a copy, not the first | ans = mid; hi = mid - 1; |
while (lo < hi) with hi = mid - 1 |
misses x when the range is one element |
a one-element range is never checked | while (lo <= hi) |
lo = mid instead of mid + 1 |
infinite loop when hi = lo + 1 |
the range stops shrinking | lo = mid + 1 |
| binary search on an unsorted array | wrong answers | the halving rule needs order | sort first, or linear search |
int total for 40 billion |
a wrong total (UB) | passes INT_MAX |
long long |
Here is the while (lo < hi) mistake for real:
#include <stdio.h>
int main() {
int a[] = {2, 5, 8, 12, 16};
int n = 5, x = 16, lo = 0, hi = n - 1, at = -1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) { at = mid; break; }
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
printf("16 at %d\n", at);
return 0;
}
Output:
16 at -1
16 is at index 4, but when the range shrinks to lo = hi = 4, the loop stops before checking it.
Your turn: the insert position (solution)
Problem. Read n sorted distinct integers, then values x. Print the index of x if it is there, otherwise the index where it would be inserted to keep the array sorted. 1 3 5 6: 5 → 2, 2 → 1, 7 → 4, 0 → 0.
Idea. The quiz: the answer is the first index with a[i] >= x (n if there is none). Binary search for it like first: when a[mid] >= x, ans = mid and go left; otherwise go right. This is called a lower bound. O(log n).
Show the solution
#include <stdio.h>
int lower_bound(int a[], int n, int x) {
int lo = 0, hi = n - 1, ans = n;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= x) {
ans = mid;
hi = mid - 1;
}
else lo = mid + 1;
}
return ans;
}
int main() {
int n, x, a[100];
scanf("%d", &n);
if (n < 0 || n > 100) {
printf("n must be 0 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (scanf("%d", &x) == 1)
printf("%d -> %d\n", x, lower_bound(a, n, x));
return 0;
}
Input 4 / 1 3 5 6 / 5 2 7 0:
5 -> 2
2 -> 1
7 -> 4
0 -> 0
Input 0 / 4:
4 -> 0
Practice questions (with solutions)
1. Integer square root. The largest r with r × r ≤ n, for 0 ≤ n ≤ 2,000,000,000, by binary search on r. Compare mid <= n / mid instead of mid * mid <= n, which would overflow.
Solution
#include <stdio.h>
int main() {
int n;
while (scanf("%d", &n) == 1) {
if (n < 0) {
printf("n must be 0 or more\n");
continue;
}
int lo = 1, hi = n, r = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (mid <= n / mid) {
r = mid;
lo = mid + 1;
}
else hi = mid - 1;
}
printf("isqrt(%d) = %d\n", n, r);
}
return 0;
}
Input 0 1 15 16 2000000000:
isqrt(0) = 0
isqrt(1) = 1
isqrt(15) = 3
isqrt(16) = 4
isqrt(2000000000) = 44721
2. Search in a sorted array rotated by k (distinct values, e.g. 6 7 9 1 3 4). At every step one half lo..mid or mid..hi is sorted; check whether x lies in the sorted half, and go there or to the other half. O(log n).
Solution
#include <stdio.h>
int search(int a[], int n, int x) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) return mid;
if (a[lo] <= a[mid]) {
if (a[lo] <= x && x < a[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (a[mid] < x && x <= a[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
int main() {
int a[] = {6, 7, 9, 1, 3, 4};
int q[] = {1, 6, 4, 9, 5};
for (int i = 0; i < 5; i++) printf("%d at %d\n", q[i], search(a, 6, q[i]));
return 0;
}
Output:
1 at 3
6 at 0
4 at 5
9 at 2
5 at -1
3. The first 1 in a sorted array of 0s and 1s. first(1) from Q2, or the lower bound of 1. -1 if there are no 1s.
Solution
#include <stdio.h>
int main() {
int a[] = {0, 0, 0, 0, 1, 1, 1};
int n = 7, lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == 1) {
ans = mid;
hi = mid - 1;
}
else lo = mid + 1;
}
printf("first 1 at %d\n", ans);
return 0;
}
Output:
first 1 at 4
Quick quiz
#include <stdio.h>
int main() {
int a[] = {1, 3, 3, 3, 5, 7};
int lo = 0, hi = 5, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= 3) { ans = mid; hi = mid - 1; }
else lo = mid + 1;
}
printf("%d\n", ans);
return 0;
}
(A) 1 (B) 2 (C) 3 (D) 0
Answer
(A) 1. mid = 2: 3 ≥ 3 → ans = 2, hi = 1. mid = 0: 1 < 3 → lo = 1. mid = 1: 3 ≥ 3 → ans = 1, hi = 0. Stop: the first 3 is at index 1.
Output:
1
Interview questions
- Linear vs binary search? Linear: O(n), any array. Binary: O(log n), sorted arrays only.
- Why
lo + (hi - lo) / 2?lo + hican overflow anint;hi - locan't. while (lo <= hi)orwhile (lo < hi)? Withhi = mid - 1andlo = mid + 1, use<=, or a one-element range is skipped.- Find the first and last occurrence in O(log n). On a match, save
midand continue left (first) or right (last). - Count occurrences of x in a sorted array. last − first + 1, two binary searches.
- What is a lower bound? The first index with
a[i] >= x; also the insert position. - How many steps does binary search need for a billion elements? About 30 (2³⁰ ≈ 1.07 billion).
- Search a rotated sorted array. One half is always sorted; check if
xis in it. - Binary search on the answer? Search a range of possible answers with a yes/no test, like the guessing game or the integer square root.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Query | One value to look up | "where is 12?" |
| Linear search | Checking elements one by one from the start | for + if (a[i] == x) |
| Binary search | Halving a sorted range every step | lo, hi, mid |
lo, hi |
The ends of the range where the answer can still be | 0, n - 1 |
mid |
The middle of the range | lo + (hi - lo) / 2 |
| log₂ n | How many times n can be halved down to 1 | log₂ 1,024 = 10 |
| O(log n) | Grows very slowly: double the input, one more step | binary search |
| Sorted | Each element ≥ the one before | 1 2 2 3 |
| Signed overflow | A signed result too big for its type: undefined behaviour | 1.5e9 + 2e9 in int |
INT_MAX |
The largest int: 2,147,483,647 |
<limits.h> |
| Undefined behaviour (UB) | The C standard makes no promise | an infinite loop here |
| First / last occurrence | The smallest / largest index holding x | 1 and 3 for 2 in 1 2 2 2 3 |
| Lower bound | The first index with a[i] >= x |
insert position |
| Binary search on the answer | Halving a range of possible answers | guessing game, isqrt |
scanf return value |
How many values it read; stops a read loop at the end | while (scanf(...) == 1) |
| Stress test | A huge input to test speed | 400,000 queries |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | 8 seconds here |
long long |
An integer of at least 64 bits | total = 40 billion |
| Rotated sorted array | A sorted array cut and swapped | 6 7 9 1 3 4 |
Summary
- Linear search is O(n) per query and times out with many queries; binary search halves a sorted range, O(log n).
- Write the middle as
lo + (hi - lo) / 2:(lo + hi) / 2overflows for big ranges (here it looped forever). - First / last occurrence: on a match, save
midand keep searching left / right. - Count = last − first + 1: two binary searches, O(log n), however many copies.
Next episode: Sorting questions I: bubble sort with an early exit, selection sort and insertion sort, with dry runs, swap counts, and stable vs unstable.