Binary Search (2017) — Computer Science

Mechanism

Repeatedly divides the search interval in half; compares target with the middle element, discards the half that can't contain the target
Precondition: data must be sorted — the single most-tested fact about this algorithm

Pseudocode

BINARY_SEARCH(arr, target):
  low = 0, high = n - 1
  WHILE low <= high:
    mid = (low + high) / 2
    IF arr[mid] == target: RETURN mid
    ELSE IF arr[mid] < target: low = mid + 1
    ELSE: high = mid - 1
  RETURN -1  // not found

Complexity

Time: O(log n) all cases (best O(1) if target is the middle element on first check)
Space: O(1) iterative; O(log n) if implemented recursively (call stack)

Why O(log n)

Each comparison eliminates half the remaining elements — search space shrinks n → n/2 → n/4 … → 1, giving log₂n steps

Exam Angle / MCQ Trap

Binary Search on an unsorted array is a classic trick question — it will give incorrect results, not just be slower. Also distinguish: this is array binary search; searching within a Binary Search Tree is a related but separate topic (see BST-Search page).

📌 Sample & Repeated FPSC Questions (2016–2026)

2026, Paper I, Q5(a) (6 marks) — Why is Binary Search not suitable for an unsorted list?

Binary Search compares the target with the middle element and discards the half guaranteed not to contain it — a guarantee that only sortedness provides. On unsorted data the target could be anywhere, so discarding a half can wrongly eliminate the half that actually holds it, giving an incorrect "not found" even when the value is present.

MCQ Trap: This is a correctness failure, not just a performance one — an unsorted array doesn't make Binary Search slower, it makes it capable of returning the wrong answer. Ties directly into this page's existing Exam Angle note.

2024, Paper I, Q6(b) (6 marks) — Write an algorithm that implements binary search recursively. Does this version have any advantages or disadvantages compared to the non-recursive version?

int binarySearchRecursive(int arr[], int low, int high, int target) {
    if (low > high) return -1;                 // not found
    int mid = low + (high - low) / 2;
    if (arr[mid] == target)
        return mid;
    else if (target < arr[mid])
        return binarySearchRecursive(arr, low, mid - 1, target);
    else
        return binarySearchRecursive(arr, mid + 1, high, target);
}

Key reasoning points:

Advantage: more concise, directly mirrors the divide-and-conquer logic — easier to read/reason about.
Disadvantage: each call adds a stack frame → O(log n) extra space for the call stack, plus function-call overhead, vs the iterative version's O(1) space and no call overhead. This is exactly why the page's Complexity section lists "Space: O(1) iterative; O(log n) if recursive" — this question is the direct code-level justification for that line.

2022, Paper I, Q7(a) (8 marks) — Draw the control flow graph for the given binary-search function and find its cyclomatic complexity.

int binarySearch(int x, int v[], int n) {
    int low, high, mid;
    low = 0; high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])       high = mid - 1;
        else if (x > v[mid])  low = mid + 1;
        else return mid;
    }
    return -1;
}

Control-flow graph has 3 decision (predicate) points: the while condition, the if, and the else if. Using $V(G) = P + 1$ :

V(G) = 3 \text{ (predicates)} + 1 = 4

Exam angle: A cross-topic question — it takes this page's exact algorithm and tests Software Engineering's cyclomatic-complexity formula on it. The answer, 4, means 4 independent test paths are needed for full branch coverage of Binary Search's while/if/else-if structure. Worth remembering that Binary Search's control structure (one loop, one two-way branch inside it) is a recurring cyclomatic-complexity example across past papers.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2024 · Paper-I · Q6(b) · 6 marks

Q. Write an algorithm that implements binary search recursively. Does this version have any advantages or disadvantages compared to the non-recursive version?

Ans.

binarySearch(A, key, low, high):
    if low > high: return -1                    // base case: not found
    mid = (low + high) / 2
    if A[mid] == key:  return mid
    if key < A[mid]:   return binarySearch(A, key, low, mid - 1)
    else:              return binarySearch(A, key, mid + 1, high)

Advantages: short, clear code that follows the "divide the problem in half" idea.
Disadvantages: each call uses a stack frame, so extra space is O(log n) (the iterative version uses O(1)). Function-call overhead makes it slightly slower.
Time: both are O(log n). The array must be sorted.

2026 · Paper-I · Q5(a) · 6 marks

Q. Why is binary search not suitable for an unsorted list?

Ans.

Binary search depends on order. It compares the key with the middle element and discards half of the list, which is correct only when all elements on one side are smaller and on the other side larger.
In an unsorted list the comparison tells nothing about which half holds the key, so discarding half can throw away the answer and return a wrong "not found".
Options: use linear search, O(n), or sort first, O(n log n), and then search in O(log n). Sorting first pays off only when many searches are made.