Searching Algorithms

The most basic search method: checks every element in order from the start of the array until it finds the target.

A very fast, high-performance search over a sorted array that repeatedly compares the middle value to halve the search range. Each iteration shrinks the candidate space by half, finding the value in a logarithmic number of comparisons.

Jumps through a sorted array in blocks of size √n to narrow the range fast, then runs a linear search inside the candidate block. The jump cost is higher than binary search, but it wins on storage where moving backward is expensive (magnetic tape, disk).

Expands the index by powers of two (1, 2, 4, 8, …) to bracket the range containing the target quickly, then runs a binary search within it. It's strong for searching unbounded or infinite streams of unknown length.

Assumes values are uniformly distributed and estimates the target's position by proportional interpolation. Faster than binary search on uniform data, but it can degrade to O(n) in the worst case on skewed distributions.

Splits the range into thirds and uses two midpoints (mid1, mid2) to discriminate three sections at once. Its recursion is shallower than binary search but it does more comparisons per step, so in practice it's mainly used to find the extremum of a unimodal function.

Partitions the range using Fibonacci numbers. Because it computes indices with only addition and subtraction — no division — it can beat binary search on hardware where division is expensive or where cache-friendly access matters.

A graph traversal that uses a FIFO queue to expand the nearest nodes first, level by level. It guarantees the shortest path in unweighted graphs and underpins shortest-distance problems, connected-component detection, and topological sorting.

A graph traversal that uses a LIFO stack to dive as deep as possible along one path, backtracking when it hits a dead end. It uses little memory (O(h)) and is central to cycle detection, topological sorting, and backtracking-based problem solving.

A heuristic-based shortest-path algorithm that expands the node with the smallest f(n) = g(n) + h(n) first. With an admissible heuristic it guarantees the optimal path, and it's the standard tool for pathfinding, game AI, and robot navigation.