Searching Algorithms

Problem: Given an array $A[0..n-1]$ and a target value $x$Determine whether $x$ exists in $A$ And return its index (or $-1$ if not found).

def linear_search(A, x):
    for i in range(len(A)):
        if A[i] == x:
            return i
    return -1

Theorem. linear_search(A, x) returns the index of the first occurrence of $x$ in $A$Or $-1$ If $x$ is not present.

Proof. The algorithm examines elements $A[0], A[1], \ldots$ in order. If $A[i] = x$It Immediately returns $i$Which is the first occurrence since all earlier elements were checked and Found not equal to $x$. If the loop completes without finding $x$Then $x \notin A$And $-1$ is Returned. $\square$

Theorem. Linear search has worst-case time complexity $O(n)$ and best-case time complexity $O(1)$.

Proof of worst case. In the worst case, $x$ is at index $n-1$ or absent. The algorithm performs $n$ comparisons. Since each comparison takes $O(1)$ time, the total is $O(n)$. $\square$

Proof of lower bound. Linear search requires $\Omega(n)$ comparisons in the worst case.

Proof. Consider an adversary argument. An adversary can answer “not equal” to the first $n-1$ Comparisons. Only after checking all $n$ elements can the algorithm conclude that $x$ is absent. Any Algorithm that does not check all $n$ positions can be fooled: the unchecked position could contain $x$. Therefore, at least $n$ comparisons are necessary in the worst case. $\square$

Problem: Given a sorted array $A[0..n-1]$ and a target value $x$Find the index of $x$ (or Determine that $x$ is not present).

def binary_search(A, x):
    low = 0
    high = len(A) - 1
    while low <= high:
        mid = (low + high) // 2
        if A[mid] == x:
            return mid
        elif A[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Theorem. binary_search(A, x) returns the index of $x$ in the sorted array $A$Or $-1$ if $x$ Is not present.

Proof. We prove by invariant.

Invariant: At the start of each loop iteration, if $x$ exists in $A$Then $x \in A[\mathrm{low}..\mathrm{high}]$.

Base case. Initially, low = 0 and high = n-1So $A[\mathrm{low}..\mathrm{high}] = A[0..n-1] = A$. If $x \in A$The invariant holds.

Maintenance. Three cases:

1. $A[\mathrm{mid}] = x$: Return mid. Correct. ✓
2. $A[\mathrm{mid}] \lt x$: Since $A$ is sorted, $A[0..\mathrm{mid}] \leq A[\mathrm{mid}] \lt x$So $x \notin A[0..\mathrm{mid}]$. Setting low = mid + 1 restricts the search to $A[\mathrm{mid}+1..\mathrm{high}]$. If $x$ was in the old range, it is in the new range.
3. $A[\mathrm{mid}] \gt x$: Since $A$ is sorted, $A[\mathrm{mid}..n-1] \geq A[\mathrm{mid}] \gt x$So $x \notin A[\mathrm{mid}..n-1]$. Setting high = mid - 1 restricts the search to $A[\mathrm{low}..\mathrm{mid}-1]$. If $x$ was in the old range, it is in the new range.

Termination. The loop terminates when low > highMeaning $A[\mathrm{low}..\mathrm{high}]$ is Empty. By the invariant, $x \notin A$. Return $-1$. ✓

$\square$

Theorem. Binary search performs $O(\log n)$ comparisons.

Proof. At each iteration, the search range is halved. Starting with a range of size $n$After $k$ iterations the range size is at most $\lceil n/2^k \rceil$. The algorithm terminates when the Range is empty, which happens when $n/2^k \lt 1$I.e., $k \gt \log_2 n$. Therefore, the maximum Number of iterations is $\lfloor \log_2 n \rfloor + 1 = O(\log n)$. $\square$

Formal derivation. Let $T(n)$ be the number of comparisons for an array of size $n$.

$T(n) = T(n/2) + O(1), \quad T(1) = O(1)$

By the Master Theorem (case 2): $T(n) = O(\log n)$.

Theorem (Binary search lower bound). Any comparison-based search algorithm on a sorted array Requires $\Omega(\log n)$ comparisons in the worst case.

Proof. A decision tree for searching a sorted array of $n$ elements has at least $n + 1$ leaves ($n$ possible positions for $x$Plus “not found”). A binary tree of height $h$ has at most $2^{h+1} - 1$ leaves, so:

$n + 1 \leq 2^{h+1} - 1 \implies h \geq \lceil \log_2(n + 2) \rceil - 1 = \Omega(\log n)$

$\square$

def binary_search_recursive(A, x, low, high):
    if low > high:
        return -1
    mid = low + (high - low) // 2
    if A[mid] == x:
        return mid
    elif A[mid] < x:
        return binary_search_recursive(A, x, mid + 1, high)
    else:
        return binary_search_recursive(A, x, low, mid - 1)

Find the position where $x$ should be inserted to maintain sorted order:

def binary_search_insert_position(A, x):
    low, high = 0, len(A)
    while low < high:
        mid = (low + high) // 2
        if A[mid] < x:
            low = mid + 1
        else:
            high = mid
    return low

Binary search can be used to find a threshold in a continuous or discrete answer space (e.g., “minimum maximum”, “maximum minimum” problems).

Problem 1. Trace linear search for the value 8 in the array [3, 1, 4, 1, 5, 9, 2, 6]. How many Comparisons are made?

Problem 2. Trace binary search for the value 25 in the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Show all iterations.

Problem 3. An array of 1024 elements is searched using binary search. What is the maximum number Of comparisons required?

Problem 4. Prove that binary search cannot be directly applied to a singly linked list, and Explain what alternative approach could achieve $O(\log n)$ search on a linked list.

Problem 5. Explain why the worst case for linear search is $\Omega(n)$ using an adversary Argument.

Problem 6. Write a function to count the number of occurrences of a value in a sorted array Using binary search. Your function should run in $O(\log n)$ time.

def count_occurrences(A, x):
    left = binary_search_insert_position(A, x)
    right = binary_search_insert_position(A, x + 1) - 1
    if left <= right and left < len(A) and A[left] == x:
        return right - left + 1
    return 0

Problem 7. Given an array that is sorted but rotated (e.g., [4, 5, 6, 7, 0, 1, 2]), write a Modified binary search that runs in $O(\log n)$ time.

def search_rotated(A, x):
    low, high = 0, len(A) - 1
    while low <= high:
        mid = (low + high) // 2
        if A[mid] == x:
            return mid
        if A[low] <= A[mid]:
            if A[low] <= x < A[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if A[mid] < x <= A[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1

Problem 8. A binary search implementation has the following bug: mid = (low + high) / 2 (using Floating-point division instead of integer division). What goes wrong?

Problem 1. Trace linear search for the value 14 in the array [7, 3, 14, 2, 9, 6, 1, 8]. How Many comparisons are made until the item is found?

Problem 2. Trace linear search for the value 5 in the array [10, 20, 30, 40, 50, 60, 70, 80, 90]. How many comparisons are made?

Problem 3. Trace binary search for the value 42 in the sorted array [3, 11, 19, 27, 35, 42, 50, 58, 66, 74]. Show all iterations with low, high, mid, and the action Taken.

Problem 4. Trace binary search for the value 15 in the sorted array [2, 6, 10, 14, 18, 22, 26, 30]. Show all iterations.

Problem 5. An unsorted array of 10,000 elements must be searched repeatedly. Compare the total Cost of using linear search directly for 1,000 queries versus sorting the array once then using Binary search for 1,000 queries.

Problem 6. A database contains 500,000 records sorted by a unique key field. Explain which Search algorithm is more efficient and calculate the maximum number of comparisons for each Algorithm.

Problem 7. Calculate the maximum number of comparisons required for binary search on arrays of Sizes 15, 100, 500, and 1,000,000. Show your working using the formula $\lfloor \log_2 n \rfloor + 1$.

Problem 8. Write pseudocode for (a) a linear search that returns the index of the first Occurrence of a target value in an array, and (b) a binary search on a sorted array that returns the Index of the target or -1 if not found.

FUNCTION LinearSearch(A, x)
    FOR i ← 0 TO LEN(A) - 1
        IF A[i] = x THEN
            RETURN i
        ENDIF
    ENDFOR
    RETURN -1
ENDFUNCTION

FUNCTION BinarySearch(A, x)
    low ← 0
    high ← LEN(A) - 1
    WHILE low ≤ high
        mid ← (low + high) DIV 2
        IF A[mid] = x THEN
            RETURN mid
        ELSE IF A[mid] < x THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

Problem 9. Trace binary search for the value 17 in the sorted array [4, 8, 12, 15, 17, 20, 24, 28, 32, 36, 40]. Show low, high, mid, and the comparison at each step.

Problem 10. (Exam-style) A school library system stores 20,000 book records. The librarian needs To: (a) search for a book by its ISBN (the catalogue is sorted by ISBN), (b) check whether a Specific book ID exists in an unsorted list of 50 recently returned books, (c) find the price of a Book given its ISBN in a sorted price catalogue. For each scenario, justify which search algorithm Is most appropriate, stating your assumptions about the data structure and ordering.

1. Forgetting that binary search requires a sorted array. Applying it to unsorted data gives incorrect results.

2. Confusing the number of comparisons with the number of elements examined in binary search.

3. Forgetting edge cases in algorithm design (e.g., empty input, single element, already sorted data).

4. Forgetting that $O(n \log n)$ average-case for quicksort becomes $O(n^2)$ worst-case on already sorted input.

5. Misunderstanding the difference between a stack (LIFO) and a queue (FIFO) in data structure applications.

6. Confusing an algorithm with a program. An algorithm is a step-by-step procedure, not its implementation in code.

1. Using binary search on an unsorted array. Binary search requires the array to be sorted. Applying it to unsorted data gives incorrect results because the comparison logic (discarding half the array) relies on the sorted order.

2. Confusing the mid calculation and causing integer overflow. Computing mid = (low + high) // 2 can overflow in languages with fixed-width integers when low + high > INT_MAX. The safe alternative is mid = low + (high - low) // 2.

3. Forgetting that binary search on a linked list is not O(log n). Binary search requires O(1) random access to the middle element. Linked lists require O(n) traversal to reach the middle, making binary search O(n) — no better than linear search.

4. Not understanding why the worst case for linear search is Ω(n). An adversary can place the target at the last position checked or declare it absent. Any algorithm that doesn’t check all n positions can be fooled. This is a lower bound, not just an observation.

5. Miscounting comparisons in binary search traces. Each iteration of binary search involves exactly one comparison (A[mid] vs target). Students sometimes count multiple comparisons per iteration or forget that the loop termination condition itself is a comparison.

The key principles covered in this topic are linked in the sub-pages above. Focus on understanding the definitions, applying the formulas or frameworks, and evaluating strengths and limitations of each approach.

Worked examples demonstrating the application of key concepts are covered in the detailed sub-pages linked above.

Searching is one of the most fundamental operations in computer science, and the two classic approaches — linear and binary search — illustrate a core trade-off: simplicity versus speed. Linear search is the obvious strategy: start at the beginning and check every item until you find what you are looking for. It works on any collection, sorted or not, but it is slow for large datasets because you might have to look at every single element. Binary search, by contrast, exploits order. By repeatedly halving the search space, it narrows down the target in logarithmic time — for a million items, it needs at most 20 comparisons instead of a million.

The key insight behind binary search is the power of eliminating half the possibilities at each step. Imagine looking up a word in a dictionary: you open it roughly in the middle, see whether your word comes before or after, and immediately discard half the pages. You repeat this until you find the word. This “divide and conquer” principle appears throughout computer science, from sorting algorithms to tree traversals. The catch is that binary search only works on sorted data, so if your data is not already ordered, you must pay the cost of sorting first — a decision that depends on how many searches you plan to perform.

In practice, the choice between algorithms depends on context. For small datasets, the overhead of binary search’s index management may not be worth it — linear search is simpler and fast enough. For large, frequently searched datasets, binary search (or its variants like interpolation search) is dramatically faster. Real-world systems often use hash tables for O(1) average-case lookups when exact matching is needed, or balanced binary search trees when both searching and ordered traversal are required. Understanding these trade-offs — data size, whether data is sorted, the cost of preprocessing, and the pattern of access — is what lets you choose the right tool for the job.