Searching: Linear and Binary Search: short notes (Algorithms)

Introduction

Searching asks whether a key $x$ occurs in a collection and, if so, where. It is one of the most basic operations, and the choice of method depends on what is known about the data:

Unsorted array. only linear search is possible, $\Theta(n)$ in the worst case.
Sorted array with random access. binary search, $\Theta(\lg n)$ in the worst case, which is optimal for comparison-based search.
Dynamic sets. binary search trees search in $O(h)$ , which can be $O(n)$ in the worst case; balanced search trees guarantee $O(\lg n)$ search with fast updates; hash tables give expected $O(1)$ search but no order.

This note treats linear and binary search, the boundary variants of binary search, and the lower bound that makes binary search optimal.

Prerequisites

Asymptotic Notation: $\Theta(n)$ versus $\Theta(\lg n)$ .
Arrays: contiguous storage and constant-time indexing.
Solving Recurrences: $T(n) = T(n/2) + 1$ .

Linear search

Purpose. Find the first index $i$ with $A[i] = x$ in an array $A[1..n]$ that may be in any order. Input. Array $A[1..n]$ , key $x$ . Output. An index $i$ with $A[i] = x$ , or NIL.

Pseudocode uses 1-based arrays, <- for assignment and A[i..j] for the subarray from position $i$ to position $j$ .

Text

LINEAR-SEARCH(A, n, x)
    for i <- 1 to n
        if A[i] = x then return i
    return NIL

Case	Key comparisons	Time
Best ( $x = A[1]$ )	1	$\Theta(1)$
Worst ( $x$ absent or last)	$n$	$\Theta(n)$
Average, $x$ present, uniform position	$(n+1)/2$	$\Theta(n)$

Space $O(1)$ . Works on linked lists and on unsorted data, needs no preprocessing, and finds the first occurrence.

Variants.

Sentinel search: store $x$ in $A[n+1]$ so that the loop needs only one test per element (while A[i] != x) instead of two (index bound and key). The count of key comparisons is unchanged in order; the constant improves.
Sorted input: linear search can stop as soon as $A[i] > x$ , which can reduce unsuccessful-search work (an expectation requires an explicit query distribution) but leaves the worst case at $\Theta(n)$ .

Binary search

Purpose. Search a sorted array in logarithmic time by repeatedly halving the range that can contain $x$ . Preconditions. $A[1..n]$ sorted in non-decreasing order, and constant-time access to any index (an array, not a linked list). Input. Sorted $A[1..n]$ , key $x$ . Output. An index $i$ with $A[i] = x$ , or NIL.

Text

BINARY-SEARCH(A, n, x)
    lo <- 1
    hi <- n
    while lo <= hi
        mid <- floor((lo + hi) / 2)
        if A[mid] = x then return mid
        else if A[mid] < x then lo <- mid + 1
        else hi <- mid - 1
    return NIL

Loop invariant. If $x$ is in $A$ , it is in $A[lo..hi]$ . Initially this is the whole array. Each comparison discards a part that cannot contain $x$ , because the array is sorted. When $lo > hi$ the range is empty, so $x$ is absent. Moreover, at that point $lo$ is the position where $x$ would be inserted to keep $A$ sorted, and $hi = lo - 1$ .

Implementation details that matter.

lo <- mid + 1 and hi <- mid - 1 guarantee progress. Writing lo <- mid with while lo < hi can loop forever when $hi = lo + 1$ .
In fixed-width integer languages such as C, compute mid = lo + (hi - lo) / 2 to avoid overflow of lo + hi.
The empty array ( $n = 0$ ) is handled: the loop does not run and NIL is returned.

Worked example

$A = [3, 8, 15, 21, 27, 34, 42, 50, 61, 77, 88]$ , $n = 11$ .

Search for 61 (present).

Probe	$lo$	$hi$	$mid$	$A[mid]$	Action
1	1	11	6	34	$34 < 61$ : $lo \leftarrow 7$
2	7	11	9	61	found, return 9

Search for 30 (absent).

Probe	$lo$	$hi$	$mid$	$A[mid]$	Action
1	1	11	6	34	$34 > 30$ : $hi \leftarrow 5$
2	1	5	3	15	$15 < 30$ : $lo \leftarrow 4$
3	4	5	4	21	$21 < 30$ : $lo \leftarrow 5$
4	5	5	5	27	$27 < 30$ : $lo \leftarrow 6$
end	6	5			$lo > hi$ : return NIL; 30 belongs at position 6

Binary search probes on the example array — Figure 1. The 11-element array searched for 30: four rows, one per probe, each showing the live range $A[lo..hi]$ shaded and $mid$ marked; the final row shows the empty range with $lo = 6$ , $hi = 5$ .

Analysis

Each probe at least halves the live range: if it has $m$ elements, the next has at most $\lfloor m/2 \rfloor$ . So the number of loop iterations is at most $\lfloor \lg n \rfloor + 1$ for $n \ge 1$ . The recurrence $T(n) = T(n/2) + \Theta(1)$ gives $\Theta(\lg n)$ by case 2 of the master theorem.

Case	Probes (three-way comparisons)	Time
Best ( $x$ at the first $mid$ )	1	$\Theta(1)$
Worst (successful or unsuccessful)	$\lfloor \lg n \rfloor + 1$	$\Theta(\lg n)$
Average, successful, uniform over positions	$\lg n - O(1)$	$\Theta(\lg n)$

Space: $O(1)$ iterative; $\Theta(\lg n)$ stack if written recursively.

A probe here is one "three-way" comparison (less, equal or greater). If the code makes two two-way comparisons per probe (= then <), the comparison count can double; read the question's counting convention.

The comparison tree. The probes binary search can make form a binary tree: the root is the first $mid$ , its left subtree handles $x < A[mid]$ and its right subtree $x > A[mid]$ . For $n = 2^k - 1$ this tree is perfect with $k$ levels. For $n = 15$ , the 15 successful searches use $1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 4 \cdot 8 = 49$ probes in total, an average of $49/15 \approx 3.27$ , against a worst case of 4. In general, for $n = 2^k - 1$ the successful searches total $\sum_{d=1}^{k} d\,2^{d-1} = (k-1)2^k + 1$ probes, and every unsuccessful search takes exactly $k$ probes, because all $n + 1$ failure leaves lie at depth $k$ .

Comparison tree of binary search for n = 15 — Figure 2. The comparison tree of binary search on $A[1..15]$ : root index 8, then 4 and 12, then 2, 6, 10, 14, then the odd indices; the 16 failure leaves sit between consecutive keys.

Lower bound

Any algorithm that searches a sorted array only by comparing $x$ with elements needs $\lceil \lg(n+1) \rceil$ three-way comparisons in the worst case. Its comparison tree must have a distinct node for each of the $n$ possible "found at $i$ " answers, and a binary tree of depth $d$ has at most $2^d - 1$ nodes, so $2^d - 1 \ge n$ . Since $\lceil \lg(n+1) \rceil = \lfloor \lg n \rfloor + 1$ , binary search is exactly optimal. Hashing beats this bound only because it does not work by comparisons.

Binary search variants

The plain version returns some matching index. With duplicates, the first or last occurrence, or a count, may be needed instead.

First occurrence (lower bound)

Text

FIRST-OCCURRENCE(A, n, x)        // smallest i with A[i] >= x, or n+1
    lo <- 1
    hi <- n + 1
    while lo < hi
        mid <- floor((lo + hi) / 2)
        if A[mid] < x then lo <- mid + 1
        else hi <- mid
    return lo

The invariant is $A[1..lo-1] < x \le A[hi..n]$ (treating $A[n+1]$ as $+\infty$ ). The loop always terminates because $mid < hi$ , so hi <- mid shrinks the range. Then $x$ is present if and only if $lo \le n$ and $A[lo] = x$ .

Replacing < by <= in the test gives the smallest $i$ with $A[i] > x$ (the upper bound). The number of occurrences of $x$ is (upper bound) minus (lower bound), found with two binary searches in $\Theta(\lg n)$ time. For $A = [2, 4, 4, 4, 7, 9]$ and $x = 4$ : lower bound 2, upper bound 5, count 3.

Binary search on a monotone predicate

Binary search works on any predicate $P(i)$ that is false for all $i$ below some threshold and true from it onwards: find the first true index in $O(\lg n)$ evaluations. Examples: the smallest $k$ with $k^2 \ge N$ (integer square root), the first bad version in a sequence of builds, or the minimum capacity that lets a schedule finish in time.

Two standard problems reduce to this form.

Fixed point. Given sorted distinct integers $A[1..n]$ , find $i$ with $A[i] = i$ . Distinct integers rise by at least 1 per step, so $A[i] - i$ is non-decreasing and $P(i) = (A[i] - i \ge 0)$ is monotone. Find the first true $i$ and test $A[i] = i$ . For $A = [-10, -5, 0, 4, 7, 9, 20]$ : probes at 4 ( $A[4] - 4 = 0$ , go left), 2 ( $-7$ , go right), 3 ( $-3$ , go right), and the answer is $i = 4$ . With duplicates allowed the predicate is no longer monotone and no $o(n)$ bound holds in general.
Maximum of a bitonic array (strictly increasing, then strictly decreasing). Use $P(i) = (A[i] > A[i+1])$ , which is false on the rising part and true from the peak on. For $A = [1, 3, 8, 12, 9, 5, 2]$ : probes at 4 ( $12 > 9$ , go left), 2 ( $3 < 8$ , go right), 3 ( $8 < 12$ , go right); the peak is at index 4. Equal neighbours break the method, so check that the question says "strictly".

Searching without a known length

To search a sorted sequence of unknown length, require an infinite sequence or a safe accessor returning an out-of-range sentinel treated as $+\infty$ . Probe index 1 first: if its value is at least $x$ , test that element (or report absence for the sentinel). Otherwise probe $2,4,8,\ldots,2^j$ until the value is at least $x$ or the sentinel is reached, then binary search the integer interval $(2^{j-1},2^j]$ with the same safe accessor, never treating the sentinel as a real match. For a present key at position $p$ , time is $O(1+\lg p)$ .

Related material. These methods are not named in the GATE syllabus. They are included because they are commonly studied together with binary search.

Ternary search splits into three parts with two comparisons per step: about $2 \log_3 n \approx 1.26 \lg n$ comparisons, more than binary search's $\lg n$ . Binary search is preferred for sorted-array membership because ternary search uses more comparisons. Ternary search also has a common application in unimodal-function optimization.
Interpolation search guesses the position from the key's value. On keys drawn uniformly at random it averages $O(\lg \lg n)$ probes, but its worst case is $\Theta(n)$ .

Important properties and observations

Binary search needs both sorted order and random access. On a sorted linked list it still costs $\Theta(n)$ because reaching the middle takes linear time.
Sorting first and then binary searching costs $\Theta(n \lg n) + k \cdot \Theta(\lg n)$ for $k$ searches; this beats $k$ linear searches only when $k$ is larger than about $\lg n$ .
Worst-case probes for $n = 1, 2, 3, 4, 7, 8, 15, 16$ : 1, 2, 2, 3, 3, 4, 4, 5. The count increases exactly when $n$ reaches a power of 2.
The final value of $lo$ in an unsuccessful search is the insertion position; this is how sorted insertion and "rank" queries are answered.

GATE examination perspective

Traces. Follow $lo$ , $hi$ and $mid$ row by row as in the worked example; common errors are rounding $mid$ up instead of down, or mixing 0-based and 1-based indices.
Counting. "maximum number of comparisons" is $\lfloor \lg n \rfloor + 1$ three-way probes; check whether two-way comparisons are counted instead.
Correctness of code variants. look for lo = mid without a matching while lo < hi and rounding rule (infinite loop), missing + 1 or - 1, and wrong loop conditions that skip the last element.
Disguised binary search. fixed point in sorted distinct integers, peak of a bitonic array, first true value of any monotone predicate: $\Theta(\lg n)$ .
Complexity traps. binary search on a linked list is $\Theta(n)$ ; counting occurrences in a sorted array is $\Theta(\lg n)$ , not $\Theta(\lg n + k)$ .

Summary

Binary Search Trees: related. The same halving idea in a dynamic, linked structure.
Hashing and Hash Functions: related. Expected $O(1)$ search without comparisons.
Solving Recurrences and the Master Theorem: prerequisite. Solving $T(n) = T(n/2) + 1$ .
Comparison of Sorting Algorithms: related. The decision-tree argument used again for sorting.

Searching: Linear and Binary Search

Introduction

Prerequisites

Linear search

Binary search

Worked example

Analysis

Lower bound

Binary search variants

First occurrence (lower bound)

Binary search on a monotone predicate

Searching without a known length

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Linear search

Binary search

Worked example

Analysis

Lower bound

Binary search variants

First occurrence (lower bound)

Binary search on a monotone predicate

Searching without a known length

Related methods

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps