Before attempting these exercises, you should read the post on linear and binary search.
Search problems are problems which ask us to find something, given a description of it. Typical search problems are like these:
- Given a list, find the index of a target value.
- Given a list of numbers, find the first negative number.
- Find the first non-empty line in a text file.
- Find all rows in an SQL database table matching a given WHERE clause.
- Given a tree, find a node which holds a target value.
- Given an HTML document, find the first
- Find all tags in an HTML document matching a given CSS selector.
- Starting at a given node in a graph, find all nodes reachable via edges.
A search algorithm is one which solves a search problem. In this post, we’ll see two algorithms which solve search problems on lists.(1)