api: YAML JSON TOON Database
version: 1.0.0
format: yaml
dataset:
  id: 2887
  slug: search-algorithms
  title: Search Algorithms
  description: Reference comparison of fundamental search algorithms.
  summary: "Searching algorithms with best, average and worst time, space and a description: linear, binary, jump, interpolation, exponential and ternary search, plus Fibonacci search, hash-based lookup and binary-search-tree lookup."
  use_when:
    - You need to choose a search method for sorted or unsorted data.
    - You need the complexity of a lookup.
  caveats:
    - Binary-search variants require sorted, randomly accessible data.
    - Hash lookup is average O(1) but needs a good hash and extra memory, and it does not support range queries.
  related:
    - sorting-algorithms
    - complexity-analysis
    - graph-traversal-algorithms
    - hash-tables
  entry_count: 9
  fields:
    - section: data
      field: name
      type: string
      example: Linear Search
    - section: data
      field: best
      type: string
      example: O(1)
    - section: data
      field: average
      type: string
      example: O(n)
    - section: data
      field: worst
      type: string
      example: O(n)
    - section: data
      field: space
      type: string
      example: O(1)
    - section: data
      field: description
      type: string
      example: Sequentially checks each element until the targ…
  category: Algorithms
  category_slug: algorithms
  tags: algorithms,search,complexity,big-o
  view_count: 50
  created_at: 1793403093
  updated_at: 1793403093
data:
  - name: Linear Search
    best: O(1)
    average: O(n)
    worst: O(n)
    space: O(1)
    description: Sequentially checks each element until the target is found.
  - name: Binary Search
    best: O(1)
    average: O(log n)
    worst: O(log n)
    space: O(1)
    description: Repeatedly divides a sorted interval in half.
  - name: Jump Search
    best: O(1)
    average: O(sqrt n)
    worst: O(sqrt n)
    space: O(1)
    description: Jumps ahead by fixed steps and then performs linear search.
  - name: Interpolation Search
    best: O(1)
    average: O(log log n)
    worst: O(n)
    space: O(1)
    description: Estimates position using interpolation for uniformly distributed data.
  - name: Exponential Search
    best: O(1)
    average: O(log n)
    worst: O(log n)
    space: O(1)
    description: Finds range by repeated doubling then binary searches within it.
  - name: Ternary Search
    best: O(1)
    average: O(log n)
    worst: O(log n)
    space: O(1)
    description: Divides the array into three parts and narrows the interval.
  - name: Fibonacci Search
    best: O(1)
    average: O(log n)
    worst: O(log n)
    space: O(1)
    description: Divides a sorted array using Fibonacci numbers, using only addition and subtraction.
  - name: Hash-Based Lookup
    best: O(1)
    average: O(1)
    worst: O(n)
    space: O(n)
    description: Computes a hash of the key to find its bucket directly.
  - name: Binary Search Tree Lookup
    best: O(1)
    average: O(log n)
    worst: O(n)
    space: O(1)
    description: Follows left and right branches by comparing keys; worst case occurs in an unbalanced tree.