Introducing Data Structures with Java

6

Searching Arrays

Arrays

Contents

• A fundamental operation on array data—searching
• Linear search and binary search algorithms
• Algorithm efficiency and O( ) notation

6.1 INTRODUCTION

Searching for an item is a common operation, whether checking a train departure timetable, looking up a phone number or using the ‘find and replace’ option in a word processor, and we shall deal with it for each structure we consider. In this chapter, we examine the process of performing searches on arrays and the methods or ‘algorithms’ used for this purpose.

6.2 A SIMPLE SEARCH STRATEGY

Imagine that an array holds data representing goods in a retail company’s ...