Source: Data Structures and Algorithms MCQ & Short Answer Review
Tags: linear search, binary search, sequential search, sorted array search, O(n), O(log n), O(1), time complexity, search algorithms, C functions, loop invariants, divide and conquer
Difficulty: Beginner Prerequisites: Basic C programming (arrays, loops, functions, return values). Familiarity with Big-O notation is helpful but covered briefly here.
Searching is one of the first algorithmic problems you encounter in a data structures course, and it underpins almost everything that follows. Linear search and binary search represent two fundamentally different strategies: brute-force iteration versus divide-and-conquer. Understanding when and why each is appropriate teaches you to reason about trade-offs between simplicity and efficiency, which is the core skill of algorithm design. If you can explain why binary search needs a sorted array and linear search does not, you already understand the central idea.
Linear search walks through an array one element at a time and runs in O(n) worst case. Binary search repeatedly halves a sorted array and runs in O(log n) worst case. Binary search is faster but requires the input to be sorted first.
Linear search (sequential search)
A search algorithm that examines each element of an array in order, from the first to the last, until it finds the target or reaches the end. Think of it as checking every seat in a cinema row until you find your friend.
Binary search
A search algorithm that works on a sorted array by comparing the target to the middle element, then discarding the half that cannot contain the target. In simple terms, it is the strategy you use when looking up a word in a physical dictionary: open near the middle, decide which half the word falls in, repeat.
Best-case time complexity
The minimum number of operations an algorithm performs on any input of size n. For linear search this is O(1), when the target happens to be the first element.
Worst-case time complexity
The maximum number of operations an algorithm performs on any input of size n. For linear search this is O(n); for binary search this is O(log n).
Loop invariant
A condition that is true before and after every iteration of a loop. In binary search, the loop invariant is that the target, if it exists, lies within the current bounds (low to high). Loop invariants help you prove that an algorithm is correct.
Sorted array
An array whose elements are arranged in non-decreasing (or non-increasing) order. Binary search requires a sorted array because its elimination logic depends on the ordering.
The function iterates from index 0 to n-1. If it finds a match, it returns the index immediately. If the loop completes without a match, it returns -1.
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i;
}
return -1;
}
Best case: O(1), the target is at position 0
Worst case: O(n), the target is absent or at the last position
No preconditions on the array; works on unsorted data
The function maintains two pointers, low and high, which define the current search window. It calculates mid, compares arr[mid] to the key, and narrows the window accordingly.
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
Best case: O(1), the target is at the midpoint on the first check
Worst case: O(log n), the search space halves each iteration
Precondition: the array must be sorted
Array: [1, 3, 5, 7, 9, 11], key = 7
Iteration 1: mid = 2, arr[2] = 5, key > 5, so low = 3
Iteration 2: mid = 4, arr[4] = 9, key < 9, so high = 3
Iteration 3: mid = 3, arr[3] = 7, match found
Index returned: 3. Three comparisons to find the element in a six-element array.
Binary search eliminates half the remaining elements by comparing the key to the middle value. If the array is unsorted, the fact that the middle element is smaller than the key tells you nothing about where the key might be. The ordering is what makes the elimination valid.
Algorithm | Best Case | Worst Case | Requires Sorted Input |
|---|---|---|---|
Linear search | O(1) | O(n) | No |
Binary search | O(1) | O(log n) | Yes |
The number of iterations binary search needs in the worst case is approximately log₂(n). For an array of 1,000,000 elements, that is roughly 20 comparisons.
Linear search is what you are doing when you scan a list of emails looking for a particular sender. Binary search is the principle behind looking up a contact in a sorted phone book, and it is used internally by database indexes and standard library functions like C's bsearch().
Students often assume binary search is always faster than linear search. If the array is unsorted, you must sort it first (O(n log n)), so for a single lookup on unsorted data, linear search is cheaper.
Students sometimes initialise high = n instead of high = n - 1. This causes an out-of-bounds read on the first iteration when mid lands at index n.
The condition arr[i] != key && i < n looks correct but evaluates arr[i] before checking whether i is in bounds. The safe order is i < n && arr[i] != key.
Returning i after a while-loop search without checking whether i == n means the function reports "found at index n" when the key is absent.
⚠️ You will almost certainly be asked to state the time complexities of both algorithms. Know them cold: linear is O(n), binary is O(log n).
⚠️ Exam questions frequently ask you to trace binary search step by step. Practise by hand on small arrays until the low/mid/high updates feel automatic.
⚠️ Bug-identification questions love the high = n vs high = n - 1 error and the bounds-check ordering error. Be ready to spot both.
⚠️ Expect a short-answer question on why binary search requires sorted input.
True or false: linear search has a best-case time complexity of O(n). Answer: False. Best case is O(1).
Fill in the blank: binary search divides the search space into ______ parts at each step. Answer: Two.
True or false: binary search can be used on an unsorted array without modification. Answer: False. The array must be sorted.
Fill in the blank: the worst-case time complexity of binary search is ______. Answer: O(log n).
True or false: if high is initialised to n instead of n - 1, binary search may access an out-of-bounds index. Answer: True.
Q: What is the main difference between linear and binary search?
A: Linear search checks each element sequentially and works on any array. Binary search divides a sorted array in half at each step and is significantly faster on large inputs.
Q: Why does binary search require a sorted array?
A: Because it relies on the ordering of elements to eliminate half of the search space at each comparison. Without ordering, the elimination logic is invalid.
Q: What is the role of loop invariants in binary search?
A: They ensure correctness by guaranteeing that, at the start of each iteration, the target (if present) lies between low and high. This condition is maintained by the way low and high are updated.
Q: Identify the bug: int low = 0, high = n; in a binary search function.
A: high should be n - 1. Setting it to n means the midpoint calculation can produce an index outside the array, causing an out-of-bounds memory access.
Q: Identify the issue with this condition: while (arr[i] != key && i < n).
A: The array access arr[i] is evaluated before the bounds check i < n. If i equals n, this reads beyond the array. The fix is to check bounds first: while (i < n && arr[i] != key), and then add a check for i == n before returning.
This material connects directly to sorting algorithms (merge sort, quicksort), because binary search is only useful once data is sorted. The divide-and-conquer strategy behind binary search reappears in merge sort and in tree-based data structures like binary search trees (BSTs). The idea of loop invariants extends to every iterative algorithm you will write in this course.
sequential search, iterative search, dichotomic search, half-interval search, logarithmic search, sorted array lookup, search algorithm complexity, Big-O notation, O(1), O(n), O(log n), C search function, array search, divide and conquer, loop invariant, bounds checking, off-by-one error, bsearch, DSA 101, Computer Science I, UCF