Introduction to Computation and Programming Using Python, second edition: With Application to Understanding Data

10.1.1 Linear Search and Using Indirection to Access Elements

A large number of problems that occur in practice can be formulated as search problems.

A search algorithm is a method for finding an item or group of items with specific properties within a collection of items. We refer to the collection of items as a search space.

10.1 Search Algorithms

It is often a good strategy to start by solving the problem at hand in the most straightforward manner possible, instrument it to find any computational bottlenecks, and then look for ways to improve the computational complexity of those parts of the program contributing to the bottlenecks.

A program that does everything in the most efficient possible way is often needlessly difficult to understand.

Keep in mind that the most efficient algorithm is not always the algorithm of choice.

10 SOME SIMPLE ALGORITHMS AND DATA STRUCTURES

We then looked at some problems (e.g., finding an approximation to the roots of a polynomial) where the search space was too large to make brute force practical.