A Textbook of Data Structures and Algorithms, Volume 3

16Searching

16.1. Introduction

Search (or searching) is a commonplace occurrence in everyday life. Searching for a book in the library, searching for a subscriber’s telephone number in the telephone directory and searching for one’s name in the electoral rolls are some examples.

In the discipline of computer science, the problem of search has assumed enormous significance. It spans a variety of applications or rather disciplines, beginning from searching for a key in a list of data elements to searching for a solution to a complex problem in its search space amidst constraints. Innumerable problems exist where one searches for patterns – images, voice, text, hypertext, photographs and so forth – in a repository of data or patterns, for the solution of the problems concerned. A variety of search algorithms and procedures appropriate to the problem and the associated discipline exist in the literature.

In this chapter, we enumerate search algorithms pertaining to the problem of looking for a key K in a list of data elements. When the list of data elements is represented as a linear list, the search procedures of linear search or sequential search, transpose sequential search, interpolation search, binary search and Fibonacci search are applicable.

When the list of data elements is represented using nonlinear data structures such as binary search trees or AVL trees or B trees and so forth, the appropriate tree search techniques unique to the data structure representation may be ...