Page 255 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures Sarabjit Kumar, Lovely Professional University

Notes Unit 14: Searching

CONTENTS
Objectives

Introduction
14.1 Linear Search
14.1.1 Characteristics

14.1.2 A Function to Implement Linear Search
14.1.3 Sequential Search on Linked Lists
14.2 Binary Search

14.2.1 Characteristics
14.2.2 Analysis
14.3 Summary

14.4 Keywords
14.5 Review Questions
14.6 Further Readings

Objectives

After studying this unit, you will be able to:
Discuss the concept of Linear Search
Define the Binary Search

Describe the characteristics of Linear Search and Binary Search
Introduction

Searching is the process of determining whether or not a given value exists in a data structure or
a storage media. Searching is an important function in computer science. Many advanced
algorithms and data structures have been devised for the sole purpose of making searches more
efficient. And as the data sets become larger and larger, good search algorithms will become
more important. At one point in the history of computing, sequential search was sufficient. But
that quickly changed as the value of computers became apparent. Linear search has many
interesting properties in its own right, but is also a basis for all other search algorithms. Learning
how it works is critical. Binary search is the next logical step in searching. By dividing the
working data set in half with each comparison, logarithmic performance, O (log n), is achieved.
That performance can be improved significantly when the data set is very large by using
interpolation search, and improved yet again by using binary search when the data set gets
smaller.

248 LOVELY PROFESSIONAL UNIVERSITY