Computer Science · Class 12 Optional

Ch 6Searching — Class 12 Computer Science, concept-first.

We store things at home and later look for them when needed. Sometimes we remember exactly where an item is kept; other times we do not, and we have to search for it. A computer works in a similar way — it stores large amounts of data and must retrieve that data later when a user or a program asks for it.

Q&A

Concepts

Not available

Exam weightage

Start learning — read this chapter →

Key concepts

Hover a concept to preview it and jump to its most relevant Q&A.

Linear Search

Imagine you have a stack of exam answer sheets on your desk, and you need to find the one belonging to a student named "Priya." You don't have them sorted alphabetically or by roll number.

Most relevant Q&A

Start with this concept →

Chapter contents

The NCERT structure, section by section. Open a section to see its questions, then read the concept-first solution.

6.1

Introduction

We store things at home and later look for them when needed. Sometimes we remember exactly where an item is kept; other times we do not, and we have to search for it.

6.2

Linear Search

3 Q

Linear search is the simplest way to find an item in a list. It works by checking every single element, one after another, from the very first element to the last.

+Worked Examples1 question

Example 6.1Assume that the numList has seven elements [8, -4, 7, 17, 0, 2, 19] so, n = 7. We need to search for the key, say 17 in numList. Table 6.1 s…Preview

+Activities1 question

Activity 6.1Consider a list of 15 elements: L=[2,3,9,7,-6,11,12,17,45,23,29,31,-37,41,43]. Determine the number of comparisons linear search makes to se…Preview

+Activities1 question

Activity 6.2In the list : L = [7,-1,11,32,17,19,23,29,31,37,43] Determine the number of comparisons linear search takes to search for key = 43.Preview

6.3

Binary Search

4 Q

Imagine you need to find the meaning of the word "Zoology" in an English dictionary. Would you start from the first page and flip through every single page until you reach Z? Of course not.

+Worked Examples1 question

Example 6.2Consider a sorted list comprising of 15 elements: numList = [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43] We need to search for the key, say 17…Preview

+Activities1 question

Activity 6.3Consider the numList [17, 8, -4, 7, 0, 2, 19]. Sort it using the sort() function of Python’s Lists. Now apply binary search to search for th…Preview

+Activities1 question

Activity 6.4Consider a list [-4, 0, 2, 7, 8, 17, 19]. Apply binary search to find element -4. Determine the number of key comparisons required.Preview

+Activities1 question

Activity 6.5For L = [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43]. Fill up the Table 6.8 for the given key values 2, 43, 17 and 9. What do you infer from T…Preview

6.3.1

Applications of Binary Search

Binary search is not just a technique for locating one value in a list — the same idea shows up, in one form or another, wherever fast lookup matters:

6.4

Search by Hashing

Hashing is a search technique designed to answer one question in a single step: Is this key present in the list? The logic is simple: if you already know exactly which index position every value shoul…

+Think & Reflect1 question

Q1Suppose a list has more than one element whose modulo division results in same remainder value. In such situations, what kind of hashing may…Preview

6.4.1

Collision

Hashing works beautifully when every element in a list maps to a unique slot in the hash table. But that ideal situation does not always happen. Consider a list like [34, 16, 2, 26, 80].

Summary

- Searching: the process of trying to locate a particular element, called the key, within a collection of elements.

Exercises

+Show 9 questions9 questions