Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Searching: linear, binary, Fibonacci and indexed sequential search

Searching: linear, binary, Fibonacci, and indexed sequential search — definitions, assumptions, time complexities, derivations, and Python implementations with sample I/O.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Searching finds a required item (key) quickly inside large data collections, which is routine in databases, file systems, log processing, compilers, and embedded systems. Choosing the right search method can reduce time and memory use drastically in production code and in systems exams.

Key ideas

  • Definition: An array is a contiguous block of memory storing elements in consecutive positions, each accessed by an integer index starting from 0 in Python and most C-like languages.
  • Definition: A sorted array is an array arranged in non-decreasing (ascending) order by key. Many search algorithms assume sorted input.
  • Definition: A comparison is a key test such as key == a[i], or key < a[i]. Search time is often measured by number of comparisons.
  • Assumption note: Unless stated, comparisons are unit-cost and each array access is O(1) in the RAM model (refer to Algorithm analysis: time and space complexity).
  1. Linear (sequential) search
  • Exact statement: Linear search scans elements one by one from the beginning until it finds the key or reaches the end.
  • Preconditions: None. The array may be unsorted and may contain duplicates. Common policy: return the first index where key is found.
  • Pseudocode idea: for i from 0 to n−1: if a[i] == key return i; after the loop return −1.
  • Comparisons derivation (successful case): average position of the first match is at (n+1)/2 when all positions are equally likely and there is exactly one match; expected comparisons = (n+1)/2. Worst case = n comparisons.
  • Comparisons derivation (unsuccessful): need to check all elements ⇒ exactly n comparisons.
  • Cost model: Time Θ(n) worst- and average-case, Θ(1) best-case (first element matches). Space Θ(1) extra.
  • Diagram to draw: A row of boxes labeled a[0]…a[n−1]. Shade boxes in order 0,1,2,… to show the scan. Mark the match at position i.
  1. Binary search
  • Exact statement: Binary search on a sorted array repeatedly halves the search interval by comparing the key with the middle element of the current interval, discarding the half where the key cannot lie, until found or interval is empty.
  • Preconditions: Array must be sorted in ascending order and support random access. No duplicates assumption is not required, but the returned index depends on the implementation (any occurrence, or first/last occurrence variant).
  • Invariant: At the start of each loop, if the key is in the array, then it is within the current low..high interval.
  • Recurrence for worst-case comparisons: T(n) = T(⌊n/2⌋) + 1 with T(1) = 1. Solution: T(n) = ⌊log₂ n⌋ + 1 comparisons in the worst case (see verify for constant/bound convention).
  • Time: O(log n) worst- and average-case; best-case O(1). Space: O(1) iterative; O(log n) if implemented recursively due to call stack (see Recursion and the stack).
  • Diagram to draw: A sorted array a[0..n−1]. Mark low, high at ends, mid = ⌊(low+high)/2⌋ at center. Show key < a[mid] discards right half by crossing it out. Repeat with new bounds.
  • Edge cases: Potential overflow in mid computation in languages with fixed-width integers; safe formula mid = low + (high−low)//2.
  1. Fibonacci search
  • Exact statement: Fibonacci search is a divide-and-conquer search on a sorted array that uses Fibonacci numbers to choose probe positions, avoiding division and using only addition/subtraction, with partition sizes following consecutive Fibonacci numbers.
  • Preconditions: Array must be sorted in ascending order; random access is required. Practical when addition is much cheaper than division (historically on some machines) or when using memory hierarchies where controlled probe distances help cache behavior.
  • Core idea: Find the smallest Fibonacci number Fm such that Fm ≥ n. Maintain an offset; compare at index min(offset + Fm−2, n−1). Based on comparison, drop to the left or right Fibonacci range, decreasing m.
  • Time: O(log n) comparisons, about log_φ(n) where φ is the golden ratio (φ ≈ 1.618), which is Θ(log n). Space: O(1) extra.
  • Diagram to draw: A sorted array with segments sized Fm−2 and Fm−1 from an offset. Label the probe index offset+Fm−2. On mismatch, shrink using the next smaller Fibonacci numbers.
  1. Indexed sequential search
  • Exact statement: Indexed sequential search augments a sorted file (or array) with a separate index that stores the maximum key (or the first key) of each fixed-size block and a pointer to that block. Search first scans the index to select a block, then performs a linear search within that block.
  • Preconditions: The main file/array is sorted; an index structure exists or can be built. The block size (number of records per block) is b, index length is about n/b.
  • Expected comparisons model: index scan ~ n/b comparisons (sequential over index) plus block scan ~ b comparisons, so total ≈ n/b + b. Minimizing n/b + b over b > 0 gives derivative −n/b² + 1 = 0 ⇒ optimal b ≈ √n. Minimum comparisons ≈ 2√n. This heuristic is standard in file-organization analysis (see verify for exact discrete bounds).
  • Time: Θ(√n) when b ≈ √n; otherwise Θ(n/b + b). Space overhead: Θ(n/b) index entries.
  • Diagram to draw: Top row: index entries I0, I1, … each showing (max-key, pointer). Bottom rows: blocks B0, B1, … of size b in sorted order. Show scanning in index until key ≤ max-key, then scanning within that block.

Definitions and theorems as exam statements

  • Definition (Successful and unsuccessful search): A successful search returns the location of the key present in the collection. An unsuccessful search returns a special value (e.g., −1) indicating absence.
  • Theorem (Comparison bounds): Any comparison-based search on an unsorted array requires n comparisons in the worst case. Proof sketch: An adversary can force checking all elements before concluding; otherwise there exists an input contradicting the answer.
  • Theorem (Binary search comparisons): For a sorted array of size n, binary search completes in at most ⌊log₂ n⌋ + 1 comparisons in the worst case and at most ⌈log₂(n + 1)⌉ comparisons in the unsuccessful case variant. Assumes unit-cost comparisons and random access (see verify for constants and ceiling/floor details).
  • Note: The above complexities are asymptotic; constants vary by implementation and platform (refer to Asymptotic notation and the step-count method).

Formulas

Programming syntax and patterns to remember:

  • for i in range(n): — loop i from 0 to n−1 inclusive of 0, exclusive of n; used for linear scan.
  • while low <= high: — condition for binary and Fibonacci search loop where the candidate interval is [low, high].
  • mid = low + (high - low) // 2 — safe midpoint without overflow; integers only.
  • a.sort() — in Python, sorts list a in ascending order in-place; required before binary/Fibonacci search if data unsorted.
  • min(x, y) — choose the smaller of x and y; used in Fibonacci probe index min(offset + Fm2, n-1).
  • bisect module (Python): bisect_left(a, key) returns insertion point to maintain sorted order; an alternative to write binary search quickly.
  • index_block = [a[min(start + b, n) - 1] for start in range(0, n, b)] — idiom to build an index of block maxima for block size b (handles the final partial block).

Worked examples

Example 1 — Model answer: Compare linear, binary, Fibonacci, and indexed sequential search. Derive optimal block size for indexed sequential.

  • Linear search: Works on unsorted data; time Θ(n) worst/average, Θ(1) best. Space Θ(1). Stable with duplicates (can return first match).
  • Binary search: Requires sorted data; time O(log n) worst/average, O(1) best; space O(1) iterative. Useful for random-access arrays and as a subroutine in many algorithms (e.g., to find lower_bound/upper_bound). Comparisons ≤ ⌊log₂ n⌋ + 1.
  • Fibonacci search: Requires sorted data; time O(log n); uses only addition/subtraction (no division); historically useful where division is expensive; similar comparison count to binary search.
  • Indexed sequential search: Requires sorted data and an auxiliary index; two-phase search: sequential over index then sequential within block. Expected comparisons ≈ n/b + b. Minimization: Let f(b) = n/b + b for b > 0. df/db = −n/b² + 1; set to zero ⇒ b = √n. Second derivative 2n/b³ > 0 ⇒ minimum. Minimum comparisons ≈ 2√n. Hence, with optimal block size, search is Θ(√n), which is between linear and binary search in efficiency and is practical for files on secondary storage where block I/O dominates.

Example 2 — Python program: Linear and Binary search Program

# Linear and Binary Search Demo
# Input: first line: space-separated integers (array)
#        second line: integer key
# Output: two lines: index from linear search, index from binary search (-1 if not found)

def linear_search(a, key):
    for i, x in enumerate(a):
        if x == key:
            return i
    return -1

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

# Read input
try:
    arr = list(map(int, input().strip().split()))
    k = int(input().strip())
except Exception:
    print("Invalid input")
    raise

# Linear search on the original array
lin_idx = linear_search(arr, k)

# Binary search requires sorted array
sorted_arr = sorted(arr)
bin_idx = binary_search(sorted_arr, k)

print(lin_idx)
print(bin_idx)

Sample input

7 2 9 4 4 11 3
4

Exact output

3
3

Explanation: Linear search returns the first match at index 3 in the original array [7,2,9,4,4,11,3]. Sorted array is [2,3,4,4,7,9,11]; binary search may return any occurrence; with the above implementation it returns index 3 (0-based) because the first mid is 3.

Example 3 — Python program: Fibonacci search and Indexed sequential search Program

# Fibonacci Search and Indexed Sequential Search Demo
# Input: first line: space-separated integers (array, not necessarily sorted)
#        second line: integer key
#        third line: integer block size b (for indexed sequential)
# Output: two lines: index from Fibonacci search on sorted array, index from indexed sequential on sorted array

def fib_search(a, key):
    n = len(a)
    # Initialize fibonacci numbers Fm = Fm2 + Fm1 with Fm2 = 0, Fm1 = 1
    fm2, fm1 = 0, 1
    fm = fm2 + fm1
    while fm < n:
        fm2, fm1 = fm1, fm
        fm = fm2 + fm1
    offset = -1
    # While there are elements to be inspected
    while fm > 1:
        # Check index fm2 from offset
        i = min(offset + fm2, n - 1)
        if a[i] == key:
            return i
        elif a[i] < key:
            # Cut the subarray from offset to i
            fm = fm1
            fm1 = fm2
            fm2 = fm - fm1
            offset = i
        else:
            # Cut the subarray after i+1
            fm = fm2
            fm1 = fm1 - fm2
            fm2 = fm - fm1
    # Check if the last element is equal to key
    if fm1 and offset + 1 < n and a[offset + 1] == key:
        return offset + 1
    return -1

def build_index(a, b):
    # Build index of block maxima (value, start_pos)
    index = []
    n = len(a)
    for start in range(0, n, b):
        end = min(start + b, n)
        max_key = a[end - 1]  # since sorted ascending
        index.append((max_key, start))
    return index

def indexed_sequential_search(a, key, b):
    # a must be sorted; b is block size
    n = len(a)
    if n == 0:
        return -1
    index = build_index(a, b)
    # 1) Scan index sequentially to find block
    block_start = 0
    for max_key, start in index:
        if key <= max_key:
            block_start = start
            break
    else:
        return -1  # key larger than all maxima
    # 2) Linear search within the block
    end = min(block_start + b, n)
    for i in range(block_start, end):
        if a[i] == key:
            return i
        if a[i] > key:
            break
    return -1

# Read input
arr = list(map(int, input().strip().split()))
key = int(input().strip())
b = int(input().strip())

# Sort for ordered searches
sarr = sorted(arr)

fi = fib_search(sarr, key)
ix = indexed_sequential_search(sarr, key, b)

print(fi)
print(ix)

Sample input

1 4 4 7 9 11 15 18 21 25
15
3

Exact output

6
6

Explanation: Sorted array is [1,4,4,7,9,11,15,18,21,25]; key 15 is at index 6. With block size b=3, the index has maxima [(4,0),(11,3),(21,6),(25,9)]; the key maps to block starting at 6, then found at 6.

Common mistakes

  • Off-by-one errors in binary search: wrong loop condition, wrong mid update, infinite loop, or missing return −1 when not found.
  • Midpoint overflow (in fixed-width languages) using (low+high)//2; prefer low + (high−low)//2.
  • Assuming binary search always returns the first or last occurrence without implementing that variant.
  • Forgetting to handle duplicates in proofs of average comparisons for linear search; state the assumption (single occurrence or uniform position of first occurrence).
  • In indexed sequential search, building the index incorrectly (e.g., storing minimum instead of maximum for ascending data), or assuming O(log n) time — it is Θ(n/b + b), minimized at Θ(√n) with uniform blocks.
  • Not resetting the offset correctly in Fibonacci search or probing indices beyond array bounds (use min(offset+Fm2, n−1)).

For your exam

  • Short notes: “When to prefer Fibonacci over binary?”, “Why is binary search O(log n)?”, “Optimal block size in indexed sequential.” Full marks: state assumptions, give formula/logic, end with conclusion (e.g., b ≈ √n).
  • Derivations: number of comparisons in linear search (successful/unsuccessful averages), T(n) for binary search, minimizing n/b + b for indexed sequential search. Full marks: write recurrence or function, solve step by step, justify minima with derivative or inequality.
  • Programs: implement binary search (iterative), Fibonacci search, or indexed sequential search. Full marks: correct loop invariants, correct mid and bounds, handle not-found case, clean I/O, and sample run.
  • Diagrams: show array, low/high/mid movement for binary search; Fibonacci partition sizes; index blocks with maxima and pointers. Full marks: labels (low, high, mid; Fm, Fm−1, Fm−2; block size b), arrows, and brief captions.

Quick check

  1. Why can’t binary search be applied directly to an unsorted array, and what’s the correct alternative?
  2. For indexed sequential search with n records and block size b, what is the approximate number of comparisons, and what b minimizes it?
  3. State the worst-case time complexity of Fibonacci search and its precondition on the data.

Answers: 1) Because binary search relies on order to discard half the array each step; use linear search (or sort, then search). 2) About n/b + b comparisons; minimized at b ≈ √n, giving ≈ 2√n. 3) O(log n); the array must be sorted in ascending order.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?