Page 267 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Binary search requires a sorted collection. This means the collection must either be sorted
before searching, or inserts/updates must be smart.
n
A binary search on an array is O(log ) because at each test you can “throw out” one half of
2
the search space.
The binary search assumes easy random-access to the data space it is searching.

14.4 Keywords

Binary Search: In binary search, we first compare the key with the item in the middle position
of the array.
Linear Search: In Linear Search the list is searched sequentially and the position is returned if the
key element to be searched is available in the list, otherwise –1 is returned.
Searching: Searching is the process of determining whether or not a given value exists in a data
structure or a storage media.

14.5 Review Questions

1. Explain the concept of searching.
2. What is linear search? Illustrate with example.
3. Discuss the complexity of linear search.

4. Discuss the characteristics of linear search.
5. Discuss the advantages of linear search over other searches.
6. Describe the steps used in implementing linear search.
7. Illustrate the use of sequential search on linked lists.
8. Explain the steps included in performing binary search.

9. Describe the analysis of binary search with example.
10. Binary searching can only be applied to a collection that allows random access. Comment.

Answers: Self Assessment

1. sequential 2. O(N)
3. worst 4. –1

5. N–1 6. Pointer
7. size 8. brute force search
9. False 10. True
11. True 12. False

13. False 14. True
15. True

260 LOVELY PROFESSIONAL UNIVERSITY