UNIT 10Prerequisite: Unit 09 — Sorting45 min read
Searching is the act of finding a specific value inside a collection of data. You have already seen linear search in Unit 02 when we searched arrays. In this unit we go deeper — understanding exactly when linear search is the right choice, and when binary search makes it hundreds of thousands of times faster.
Binary search is one of the most elegant ideas in all of computer science. A simple trick — always check the middle — that turns a million-item search into just 20 steps. We will understand it completely, implement it two ways, and learn its most useful variations.
// Section 1
Linear Search — Check Every Element
Linear search is the simplest possible search strategy: start from the first element and check each one in order until you either find the target or reach the end. No tricks, no requirements. Works on any array — sorted or unsorted.
// Searching for 7 in [3, 9, 2, 7, 5, 1, 8] — check one by one
Check index 0: arr[0]=3 ≠ 7 → continue
Check index 1: arr[1]=9 ≠ 7 → continue
Check index 2: arr[2]=2 ≠ 7 → continue
Check index 3: arr[3]=7 = 7 → FOUND ✓
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
int i;
for (i = 0; i < n; i++) {
if (arr[i] == target) {
return i; /* found — return the index */
}
}
return -1; /* not found — -1 is the universal "not found" signal */
}
int main() {
int arr[] = {3, 9, 2, 7, 5, 1, 8};
int n = 7;
int result = linearSearch(arr, n, 7);
if (result != -1) {
printf("Found 7 at index %d\n", result); /* Found 7 at index 3 */
} else {
printf("Not found\n");
}
/* searching for something not in the array */
result = linearSearch(arr, n, 99);
printf("Search for 99: %d\n", result); /* -1 */
return 0;
}
Best Case:O(1)(target at index 0)
Worst Case:O(n)(target at end or absent)
When is linear search the right choice?
✓Array is unsorted and sorting first would cost more than searching
✓Array is small (fewer than ~100 elements) — overhead of other methods is not worth it
✓You only need to search once — no repeated searches on the same data
✗Array is sorted — binary search is dramatically faster
✗You search the same data repeatedly — sort once, binary search many times
// Section 2
Binary Search — The Half-Every-Step Idea
Binary search works on a sorted array only. The insight is simple and powerful: if you check the middle element and it is too big, the target must be in the left half. If it is too small, the target must be in the right half. Either way you eliminate half the remaining elements with every single check.
📖 How you already use binary search every day
When you look up a word in a physical dictionary, you do not start from page 1 and flip through every page. You open somewhere in the middle. If the word you need comes after what you see, you open the right half. If it comes before, you open the left half. You keep halving until you land on the right page. That is binary search — you have been doing it your whole life.
Linear approach
1000-page dictionary. Looking for "Zebra." You start at page 1 and flip one page at a time. You reach page ~950 after ~950 flips. Painful.
Binary approach
Open page 500 → too early. Open page 750 → still early. Open page 875... You find "Zebra" in about 10 flips. Always.
How many steps does binary search actually need?
| Array size (n) | Linear search (worst) | Binary search (worst) | How much faster |
|---|
| 100 | 100 | 7 | 14× |
| 1,000 | 1,000 | 10 | 100× |
| 1,000,000 | 1,000,000 | 20 | 50,000× |
| 1,000,000,000 | 1,000,000,000 | 30 | 33,000,000× |
Binary search steps = log₂(n). Every time you double n, you only need 1 more step.
// Section 3
Binary Search — Step by Step Trace
Let us trace binary search on a sorted array to see every decision clearly. We search for target = 23 in [2, 5, 8, 12, 16, 23, 38, 45, 67, 91]
// blue = low/high boundary · green = mid being checked · faded = eliminated
Step 1: low=0, high=9, mid=4 → arr[4]=16 < 23 → search RIGHT half
Step 2: low=5, high=9, mid=7 → arr[7]=45 > 23 → search LEFT half
Step 3: low=5, high=6, mid=5 → arr[5]=23 = target → FOUND ✓
Found 23 at index 5 in just 3 steps — linear search would have needed 6 steps
// Section 4
Binary Search — Iterative Version
The iterative version uses a loop with three pointers — low, high, mid. Each iteration either finds the target or narrows the search window by half. This is the version most commonly asked in interviews.
#include <stdio.h>
int binarySearch(int arr[], int n, int target) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
/* Note: use low + (high-low)/2 instead of (low+high)/2
to avoid integer overflow when low and high are large */
if (arr[mid] == target) {
return mid; /* found — return index */
} else if (arr[mid] < target) {
low = mid + 1; /* target is in the RIGHT half */
} else {
high = mid - 1; /* target is in the LEFT half */
}
}
return -1; /* low > high — target not in array */
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 67, 91};
int n = 10;
printf("Search 23: index %d\n", binarySearch(arr, n, 23)); /* 5 */
printf("Search 2: index %d\n", binarySearch(arr, n, 2)); /* 0 */
printf("Search 91: index %d\n", binarySearch(arr, n, 91)); /* 9 */
printf("Search 50: index %d\n", binarySearch(arr, n, 50)); /* -1 */
return 0;
}
Best Case:O(1)(target is the middle element)
Worst Case:O(log n)
Space:O(1)
⚠️ Important
The overflow bug: Writing mid = (low + high) / 2 can cause integer overflow when low and high are both large numbers — their sum exceeds the maximum int value. Always write mid = low + (high - low) / 2 instead. This is a well-known bug that existed in Java's standard library for years.
// Section 5
Binary Search — Recursive Version
The recursive version expresses the same logic using function calls instead of a loop. The base cases: array is empty (low > high) → not found. Middle element matches → found. Recursive cases: search left half or right half.
#include <stdio.h>
int binarySearchRecursive(int arr[], int low, int high, int target) {
/* base case: search space is empty */
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid; /* found */
} else if (arr[mid] < target) {
/* search right half */
return binarySearchRecursive(arr, mid + 1, high, target);
} else {
/* search left half */
return binarySearchRecursive(arr, low, mid - 1, target);
}
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 67, 91};
int n = 10;
printf("Search 23: index %d\n",
binarySearchRecursive(arr, 0, n-1, 23)); /* 5 */
printf("Search 38: index %d\n",
binarySearchRecursive(arr, 0, n-1, 38)); /* 6 */
printf("Search 99: index %d\n",
binarySearchRecursive(arr, 0, n-1, 99)); /* -1 */
return 0;
}
Iterative version
O(1) space — no call stack frames. Preferred in production and interviews where stack depth could be a concern on very large arrays.
Recursive version
O(log n) space — one call per level. Cleaner and easier to understand. Good for learning and for variations that naturally require recursion.
// Section 6
Binary Search Variations — The Interview Favourites
Standard binary search finds a position of the target. But interviewers often ask variations. These four come up constantly — learn the subtle changes that make each one work.
Variation 1 — Find First Occurrence of a Repeated Value
In [1, 2, 2, 2, 3, 4], finding 2 could return index 1, 2, or 3. How do you always return the first one (index 1)? When you find the target, do not stop — save the index and keep searching left.
int firstOccurrence(int arr[], int n, int target) {
int low = 0, high = n - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid; /* save this position */
high = mid - 1; /* keep searching LEFT for an earlier occurrence */
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
/* firstOccurrence([1,2,2,2,3,4], 6, 2) → 1 */
Variation 2 — Find Last Occurrence of a Repeated Value
Same idea, opposite direction. When you find the target, save the index and keep searching right for a later occurrence.
int lastOccurrence(int arr[], int n, int target) {
int low = 0, high = n - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid; /* save this position */
low = mid + 1; /* keep searching RIGHT for a later occurrence */
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
/* lastOccurrence([1,2,2,2,3,4], 6, 2) → 3 */
Variation 3 — Count Total Occurrences
Once you have first and last occurrence, count = last - first + 1. O(log n).
int countOccurrences(int arr[], int n, int target) {
int first = firstOccurrence(arr, n, target);
if (first == -1) return 0; /* target not in array */
int last = lastOccurrence(arr, n, target);
return last - first + 1;
}
int main() {
int arr[] = {1, 2, 2, 2, 3, 4, 4, 5};
int n = 8;
printf("Count of 2: %d\n", countOccurrences(arr, n, 2)); /* 3 */
printf("Count of 4: %d\n", countOccurrences(arr, n, 4)); /* 2 */
printf("Count of 6: %d\n", countOccurrences(arr, n, 6)); /* 0 */
return 0;
}
Variation 4 — Search in a Rotated Sorted Array
A sorted array has been rotated at some pivot: [4, 5, 6, 7, 0, 1, 2]. Standard binary search breaks here. The fix: one of the two halves is always sorted — check which half is sorted, and use that to decide which half the target could be in.
// [4, 5, 6, 7, 0, 1, 2] — sorted [0,1,2,3,4,5,6] rotated at index 4
left half: sorted [4,5,6,7] right half: sorted [0,1,2] int searchRotated(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid; /* found */
/* check which half is sorted */
if (arr[low] <= arr[mid]) {
/* LEFT half is sorted */
if (target >= arr[low] && target < arr[mid]) {
high = mid - 1; /* target is in the sorted left half */
} else {
low = mid + 1; /* target must be in the right half */
}
} else {
/* RIGHT half is sorted */
if (target > arr[mid] && target <= arr[high]) {
low = mid + 1; /* target is in the sorted right half */
} else {
high = mid - 1; /* target must be in the left half */
}
}
}
return -1;
}
int main() {
int arr[] = {4, 5, 6, 7, 0, 1, 2};
int n = 7;
printf("Search 0: index %d\n", searchRotated(arr, n, 0)); /* 4 */
printf("Search 6: index %d\n", searchRotated(arr, n, 6)); /* 2 */
printf("Search 3: index %d\n", searchRotated(arr, n, 3)); /* -1 */
return 0;
}
Time:O(log n)— same as standard binary search
// Section 7
Bonus — Find Where to Insert (Lower Bound)
A very common interview question: given a sorted array and a target, find the index where target should be inserted to keep the array sorted. If it already exists, return its first position. When the loop ends, low always holds the correct insertion index — because it is the first position where the value is ≥ target.
#include <stdio.h>
int lowerBound(int arr[], int n, int target) {
int low = 0, high = n; /* note: high = n, not n-1 */
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target) {
low = mid + 1; /* target goes to the RIGHT */
} else {
high = mid; /* arr[mid] >= target — could be insertion point */
}
}
return low; /* insertion index */
}
int main() {
int arr[] = {1, 3, 5, 6};
int n = 4;
printf("Insert 5: index %d\n", lowerBound(arr, n, 5)); /* 2 — exists at 2 */
printf("Insert 2: index %d\n", lowerBound(arr, n, 2)); /* 1 — between 1 and 3 */
printf("Insert 7: index %d\n", lowerBound(arr, n, 7)); /* 4 — after the end */
printf("Insert 0: index %d\n", lowerBound(arr, n, 0)); /* 0 — before start */
return 0;
}
// Section 8
Decision Guide — Which Search to Use
If: Array is unsorted AND you only search once
→ Linear Search — O(n). Sorting to binary search would cost O(n log n) more.
If: Array is unsorted AND you will search many times
→ Sort it first (O(n log n)), then use Binary Search (O(log n) per query). The sort cost is paid once.
If: Array is sorted
→ Always Binary Search — O(log n). Never waste time with linear search on sorted data.
If: Array is sorted and has repeated values, need first/last position
→ Binary Search variation — firstOccurrence() or lastOccurrence(). Still O(log n).
If: Array is sorted but has been rotated
→ Rotated binary search — identify the sorted half first, then decide direction. O(log n).
If: Data is in a hash table (Unit 14)
→ Direct lookup — O(1). Faster than both for point queries.
// Errors You Will Hit
Common Binary Search Mistakes
⚠ Using binary search on an unsorted array
Symptom: Incorrect results — sometimes finds the target, sometimes misses it
Fix: Binary search only works on sorted data. Always sort first or verify the array is sorted.
⚠ Off-by-one in the loop condition
Symptom: Missing the last element or going into an infinite loop
Fix: Use while (low <= high) — the <= is essential. Without it, when low == high you skip checking the last candidate.
⚠ Forgetting mid + 1 and mid - 1
Symptom: Infinite loop — low and high never converge
Fix: When you move the boundary, always move it past mid: low = mid + 1 or high = mid - 1. Never set low = mid or high = mid in standard search.
// What's Next
You Are Ready for Unit 11
You now have a complete toolkit for searching — linear search for unsorted data, binary search for sorted data, and four powerful variations for the most common interview scenarios. The overflow-safe midpoint formula and the first/last occurrence patterns alone will save you in dozens of future problems.
In Unit 11 we enter the world of Trees — hierarchical data structures that look like upside-down trees. Trees are everywhere: file systems, HTML pages, databases, compilers. We build binary trees from scratch, learn all four traversal orders, and understand the properties that make trees so powerful.
UP NEXT → UNIT 11
Trees — Hierarchical Data
Binary trees, inorder, preorder, postorder, level order — built in C.
🎯 Key Takeaways
- ✓Linear search checks every element one by one — O(n) worst case, works on unsorted data
- ✓Binary search requires sorted data — cuts the search space in half every step — O(log n)
- ✓For 1 billion elements: linear search = 1 billion steps, binary search = just 30 steps
- ✓Always use mid = low + (high - low) / 2 — never (low + high) / 2 to avoid integer overflow
- ✓Loop condition is while (low <= high) — the <= matters, not just <
- ✓Always move past mid: low = mid + 1 or high = mid - 1 — never set to mid itself
- ✓First occurrence: when found, save index and search left (high = mid - 1)
- ✓Last occurrence: when found, save index and search right (low = mid + 1)
- ✓Count occurrences = lastOccurrence - firstOccurrence + 1 — still O(log n)
- ✓Rotated array search: identify the sorted half, check if target is in that half, decide direction