Introduction

Searches are used to find solutions to problems and there are many ways to search for a solution. Here are some generic searches that can be applied to many different problems.

Binary Search

Binary search is a type of search that is able to find an object in a sorted list in O(log n). In binary search we first start at the middle element and we keep trying to halve the problem until we find the element we need.

Ternary Search

Ternary search is a type of search that finds the maximum value of a increasing or decreasing function by breaking it into 3 parts.

Depth First Search

Depth first search or DFS is a method of search that goes as far as possible before backtracking. DFS is implemented using a stack and most of the time it uses an function stack for recursion.

Breadth First Search

Breadth first search or BFS is a method of search that takes the closest things first then the farthest. BFS is implemented with a queue.

Flood Fill

Flood fill is a search that fills a grid. It can be implemented with either DFS or BFS. We first start at some starting position and then we expand in the directions that we can (eg: up, left, down, right).

Backtracking

Backtracking is a search that enumerates every single possible solution by using partial solutions.