api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2477
  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[2]: You need to choose a search method for sorted or unsorted data.,You need the complexity of a lookup.
  caveats[2]: "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[4]: sorting-algorithms,complexity-analysis,graph-traversal-algorithms,hash-tables
  entry_count: 9
  fields[6]{section,field,type,example}:
    data,name,string,Linear Search
    data,best,string,O(1)
    data,average,string,O(n)
    data,worst,string,O(n)
    data,space,string,O(1)
    data,description,string,Sequentially checks each element until the targ…
  category: Algorithms
  category_slug: algorithms
  tags: "algorithms,search,complexity,big-o"
  view_count: 46
  created_at: 1792832553
  updated_at: 1792832553
data[9]{name,best,average,worst,space,description}:
  Linear Search,O(1),O(n),O(n),O(1),Sequentially checks each element until the target is found.
  Binary Search,O(1),O(log n),O(log n),O(1),Repeatedly divides a sorted interval in half.
  Jump Search,O(1),O(sqrt n),O(sqrt n),O(1),Jumps ahead by fixed steps and then performs linear search.
  Interpolation Search,O(1),O(log log n),O(n),O(1),Estimates position using interpolation for uniformly distributed data.
  Exponential Search,O(1),O(log n),O(log n),O(1),Finds range by repeated doubling then binary searches within it.
  Ternary Search,O(1),O(log n),O(log n),O(1),Divides the array into three parts and narrows the interval.
  Fibonacci Search,O(1),O(log n),O(log n),O(1),"Divides a sorted array using Fibonacci numbers, using only addition and subtraction."
  Hash-Based Lookup,O(1),O(1),O(n),O(n),Computes a hash of the key to find its bucket directly.
  Binary Search Tree Lookup,O(1),O(log n),O(n),O(1),Follows left and right branches by comparing keys; worst case occurs in an unbalanced tree.