searching algos

linear

check every element from start to end

binary

pick middle element and compare, choose right or left subarray and pick middle, …

sentinel linear

set last element to target (save last element as variable), linear search (don’t need to compare last element), see if index is less than array length or last (saved element) is same as target. guarantees that search will terminate so don’t have to check that index < array length (e.g. use while instead of for to reduce index comparison)

ternary

divide array into 3 parts instead of 2 and do binary search, pick subarray and check recursively

jump

for sorted arrays, search at sqrt(n) index, then increase by sqrt(n) until either index is greater than array size or item >= target, then linear search in block if index <= array size

interpolation

estimate binary search index assuming uniform distribution

idx = low + ((target-arr[low]) * (high-low) // (arr[high]-arr[low]))

exponential

for sorted array but don’t know array size or target near beginning, check index=0, then start at index=1 and double to find range of where target < index, then binary search in range

fibonacci

where division is expensive, find smallest fibonacci >= len array, while it’s >1, use index=min(smallest fib - offset, len array - 1)

if element at index <target: decrement fibonacci, offset=index

else if >target: fib, fib1, fib2 = fib2, fib1-fib2, fib-fib1 where fib > fib1 > fib2

if still not found, check if index=offset+1 == target

best first

init visited set, heap pop from start, add node to visited, for neighbors add to heap (use heuristic, must be calculated otherwise)

bfs

check node, iterate through children and append to queue then pop from queue

dfs

check node, iterate through children and add to stack then pop off stack

meta binary

computes the difference between the value of the middle element and the value of the target element, and divides the difference by a predetermined constant, usually 2. This result is then used as the size of the new interval.

optimized: build up boundary using left bitshift and +1, then iterate backwards from that boundary to -1, check indices using incremental search index where adding 1«i using iteration value. avoids division so cache friendly