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: