Searching

Searching algorithm are those that set out to find a target value. In addition to the value, they might also provide details on how to get to it. Searching is often synonymous with traversal.

To-do

  • Searching
    • Iteratively-Deepening Depth-First Search
    • Best-First Search
      • Dijkstra
      • A*
      • Iteratively-Deepening A*
      • JPA*
      • …
    • Graph: Minimum-Spanning-Tree
  • When to use each algorithm!

Quickselect

#quick-sort#quickselect#search#traverse#selecting-k-elements

Hoare’s Selection Algorithm to find the kth order statistic in an unordered list.

Select K Elements Pattern

#search#traverse#heap#smallest-element#largest-element#min-heap#max-heap#quickselect

A pattern to efficiently find the K-largest/smallest/most-frequent elements in an array using a heap.

Monotonic Stack

#search#traverse#dynamic-programming#stack#monotonic-stack#smallest-element#largest-element

Technique used to for finding the next greater, or smaller element in an array.

Fast & Slow Pointer

#search#traverse#dynamic-programming#sliding-window#fast-slow-pointer#two-pointers#tortoise-and-hare#cycle-detection#remove-duplicates#linked-list

Technique to detect cycles, duplicates or other relationships in a container.

Two Pointers

#search#traverse#dynamic-programming#sliding-window#two-pointers#palindrome#two-sum-problem#trapping-water

Algorithm using two pointers or indices into an array to optimize complex problems.

Sliding Window

#search#traverse#dynamic-programming#sliding-window

A technique to solve problems over a sub-range (window) of the input data.

Binary Search

#search#binary-search

Finds the position of a target value within a sorted array, by iteratively halving the input array.

Breadth-first Search

#search#bfs#binary-first-search

Used for searching graph data structures for a node that satisfies a given property. It starts a given node (the root for a tree), and explores all directly connected nodes before moving on to nodes at the next depth level. Extra memory, usually a queue, is used to keep track of child nodes not-yet explored. NB: The algorithm can be applied to an implicit tree (where the next nodes are discovered while iterating).

Depth-first Search

#search#dfs#depth-first-search

Used for searching graph data structures for a node that satisfies a given property. It starts a given node (the root for a tree), and explores as far as possible along each branch before backtracking to the next. Extra memory, usually a stack, is used to keep track of child nodes not-yet explored (for backtracking). NB: The algorithm can be applied to an implicit tree (where the next nodes are discovered while iterating).