4 Looking and finding

 

This chapter covers

  • How computer programs are made
  • Building a simple computer program for searching
  • Measuring and improving a program’s speed

When writing a book, it is important to be able to efficiently wrangle a long piece of text. One important task is to search for a word, finding where it has been used. We may then jump to such a position in the text, see what is around the word, and modify or replace it. We need to do this on demand, without an explicitly prepared index. In fact, we have indexes at the back of books because searching through the book manually, from front to back, is slow and error prone for a human. Luckily, it is fast and accurate for a computer. In this chapter, we will learn how to write a computer program to search text and then improve it to measure and increase the search speed.

4.1 A simple method

It might seem that it is easy to describe to a computer how to search for a word: just look for it! But we must prepare an explicit method, made of tiny little simple steps for the computer to follow. Everything must be explained in perfect detail—no big assumptions, no hand waving. Such a careful, explicit method is called an algorithm.

4.2 Writing a program

4.3 Speed

4.4 A faster algorithm

4.5 Problems

4.6 Summary