NCERT Class 12 Computer Science Chapter 6: Searching

This page gives you the official NCERT Class 12 Computer Science Chapter 6 Searching PDF from the current NCERT edition, and explains what is inside it. The chapter runs 16 pages and teaches the three standard ways to locate a key in a collection: linear search, binary search and search by hashing.

Whether you want the searching class 12 PDF itself or a clear explanation of how each method works, both are here — the download comes first, the teaching below it.

Download the searching class 12 NCERT chapter PDF

The official file is at NCERT Class 12 Computer Science Chapter 6 Searching PDF on ncert.nic.in — open it to read the chapter exactly as printed, including the algorithms, the Python programs, the trace tables and the exercise set at the end. The page below explains what each of those parts teaches.

Chapter 6 Searching at a glance

The table in this section shows what the chapter holds — its sections, activities, tables, equations and exercise questions — so you can see the size of the file before opening it. The chapter itself is organised into four sections:

• Introduction — what searching means and why it matters
• Linear Search — item-by-item comparison, with Algorithm 6.1 and Program 6-1
• Binary Search — halving a sorted list, with Algorithm 6.2 and Program 6-2
• Search by Hashing — direct position lookup, with the remainder method and Program 6-3

What this chapter teaches: three ways to find an item

Searching means locating a particular element, called the key, in a collection of elements. The search determines whether the key is present and, if it is, where it sits in the collection (NCERT, p. 1). The chapter offers three completely different strategies for that job.

Linear search is the baseline. It compares the key with every element of the list, from the first to the last, until a match is found or the list ends (NCERT, p. 2). It needs no ordering — it works on any list — but in the worst case it compares all n elements.

Binary search is the sorted-list shortcut. The chapter opens it with the dictionary example: to find “Zoology” you go straight to the second half, because dictionary words are in alphabetical order (NCERT, p. 5). Binary search compares the key with the middle element, then repeats the search in only one half.

Search by hashing is the direct method. Instead of comparing at all, it computes where the key should be using a formula called a hash function, then checks that single slot (NCERT, p. 10).

The three key ideas, explained

Linear search: compare every element in order

Linear search is exhaustive: it checks the first element, then the second, and so on until the key is found or the list runs out. The chapter’s Algorithm 6.1 starts with index = 0 and moves index upward by one each time the comparison fails (NCERT, p. 2). Here is an original trace — numList = [5, 12, 9, 21, 3], key = 9:

The search makes 3 comparisons and reports the key at position 3 — index + 1, because positions count from 1 while list indexing starts at 0. The best case is the key at the first position: only 1 comparison needed. The worst case is the key at the last position, or absent entirely: all n comparisons (NCERT, p. 3).

Program 6-1 does the same job in Python, returning index+1 on success and None on failure (NCERT, p. 4).

Binary search: halve a sorted list each time

Binary search works only on a list that is already ordered — ascending or descending for numbers, alphabetical for words (NCERT, p. 5). It compares the key with the middle element. Three outcomes are possible: a match (search ends), the middle element is larger than the key, or it is smaller.

If the middle element is larger, the key, if present, can only be in the first half — the second half is discarded in one step. If it is smaller, the key is in the second half (NCERT, p. 5). Each unsuccessful comparison still tells you which half could hold the key, which is why each step roughly halves the search area.

Trace an original example: sorted list [4, 9, 15, 22, 30, 41, 55, 63], key = 30. The mid position is always \( (\text{first} + \text{last}) // 2 \) (Algorithm 6.2, NCERT, p. 7):

Notice the search area: 8 elements, then 4, then 1 — halving each iteration. The loop runs while first is less than or equal to last; once first passes last, no element remains and the search is unsuccessful (NCERT, p. 7).

For an even-sized list the // operator matters: 10 elements give mid = 10 // 2 = 5, so the sixth element is treated as the middle, leaving 5 elements in the first half and 4 in the second (NCERT, p. 5).

Search by hashing: compute the position directly

Hashing aims for a single comparison. If we already know which slot an element lives in, checking the key takes one step. The chapter’s remainder method uses a hash function \( h(\text{element}) = \text{element} \;\%\; \text{size} \), and the remainder becomes the element’s index (NCERT, p. 10).

With the book’s own list [34, 16, 2, 93, 80, 77, 51] and a 10-slot table, element % 10 gives the indices 4, 6, 2, 3, 0, 7 and 1, so the hash table fills slots 0–7 and leaves slots 5, 8 and 9 empty (NCERT, p. 10). Searching for 16 now means: compute 16 % 10 = 6, check slot 6 — one comparison, found.

Now an original example that shows the catch. Take the list [23, 47, 15, 5, 52, 18] with the same 10-slot table:

Elements 15 and 5 both map to slot 5. If 5 is inserted after 15, slot 5 holds 5 and the original 15 is lost.

Searching for 15 computes 15 % 10 = 5 and checks slot 5, only to find the value 5 sitting there. The program returns None — “not present” — even though 15 was in the original data.

This situation, where two elements map to the same slot, is called a collision (NCERT, p. 12), and it breaks the one-comparison guarantee. Hashing stays ideal only when every element maps to a unique slot.

How the chapter’s trace tables teach searching

This chapter has no diagrams — it is text-and-table based, and its Tables 6.1–6.10 do the teaching that figures do in other chapters. It is worth learning to read them, because the exercises ask you to draw exactly these tables.

A linear search trace table (like Tables 6.2 and 6.4) has one row per comparison. Columns track the current index, the check whether the index is still within range, whether the element equals the key, and the next index.

Reading top to bottom you see the search’s work: Table 6.2 shows 4 comparisons when the key sits at position 4; Table 6.4 shows just 1 when the key is at position 1; a missing key would run all n rows (NCERT, pp. 2–3).

A binary search trace table (like Table 6.7) tracks first, last and mid per iteration. The book’s own example searches key 2 in a 15-element sorted list: the list shrinks from 15 elements, to 7, to 3, to 1, and the fourth iteration finds the key (NCERT, p. 8). That is halving made visible.

The hash table (Tables 6.8–6.10) is a row of slots indexed 0–9. Empty slots hold the value None; each inserted element sits at the index its hash function produced (NCERT, p. 11).

Definitions you should be able to write

The chapter introduces a small set of terms. If a question asks you to define one of them, or to explain what it does, this list covers it:

• Searching — locating a particular element, called a key, in a collection; the result states whether the key is present and where (NCERT, p. 1).
• Key — the item being searched for in the list (NCERT, p. 2).
• Linear (sequential/serial) search — an exhaustive technique that compares the key with every element one by one, in list order, until a match or the end of the list (NCERT, p. 2).
• Binary search — a search that uses the ordering of a sorted list, comparing the key with the middle element and repeating the search in only one half (NCERT, p. 5).
• Hash function — a formula that takes an element and generates its index value in a hash table (NCERT, p. 10).
• Hash table — the list formed by placing each element at the index its hash function produced; each index holds one item (NCERT, p. 10).
• Remainder method — a hash function that divides the element by the table size; the remainder is the hash value (NCERT, p. 10).
• Hash value — the remainder produced by the hash function (NCERT, p. 10).
• Collision — the situation in which two different elements map to the same slot of the hash table (NCERT, p. 12).
• Collision resolution — the mechanism for placing the second and later items that share a hash value (NCERT, p. 12).
• Perfect hash function — a hash function that maps every element to a unique index, so collisions never occur (NCERT, p. 12).

One scope note: the chapter defines collision resolution but states the methods are beyond its scope (NCERT, p. 12), so you need to know what it is for, not how to implement it.

Common mistakes students make in this chapter

These are the errors the chapter’s own material sets up — knowing them before you trace avoids them:

Using the chapter for exam preparation

Every exercise in this chapter tests one of the three methods, so mastering one exercise per method covers the chapter’s ideas. Here is what each question actually asks:

• Exercises 1 and 2 — linear search tracing and duplicate handling. Exercise 1 asks for a full trace table for four keys; Exercise 2 asks what position is returned when key 8 appears twice in the list (answer: the first match — position 4).
• Exercises 3 and 4 — writing the programs. Exercise 3 is linear search on a list with negative and positive numbers; Exercise 4 is binary search on 10 integers.
• Exercises 5 and 6 — comparing the methods on the same data. Both ask you to count linear search comparisons before and after sorting, then count binary search iterations after sorting.
• Exercise 7 — the big-number interpretation. With \( 2^{30} \) = 1,073,741,824 sorted records and the target at the middle, linear search needs about \( 2^{29} \approx 536 \) million comparisons, while binary search’s very first comparison lands on that middle element. The point: binary search’s halving logic is what makes huge sorted databases searchable.
• Exercises 8 and 9 — building hash tables. Exercise 8 uses \( h(\text{element}) = \text{element} \;\%\; 11 \); Exercise 9 uses the length of a country name as the hash function, with index = length − 1, so India (5 letters) sits at index 4, as the chapter shows.

The chapter’s activities are mini-versions of these exercises — each asks you to count comparisons or iterations on a given list before reading the worked answer. The efficiency contrast between the three methods is summarised below:

Chapter 6 revision summary

A two-minute recap of what the chapter concludes, from its own SUMMARY (NCERT, p. 13):

• Searching locates a key in a collection and reports whether it is present and where.
• Linear search checks elements one at a time without skipping any; it suits small unsorted lists but slows down as the list grows.
• Binary search takes a sorted list, compares the key with the middle element, and repeats the search in only the half that could contain the key, until the key is found or one element remains.
• An unsuccessful binary search comparison is not wasted — it reveals which half holds the key and narrows the search area.
• Hashing needs only one key comparison when every element sits at the position its hash function assigns.
• Two elements landing in the same slot is a collision; placing the second and later items is collision resolution.
• A perfect hash function maps each key to a unique index, so collisions never occur.

Related resources

This listing is maintained for the 2026-27 academic session using the NCERT textbook information available to us. NCERT remains the authority for confirming the latest edition.

Continue revising from the same site: Class 12 Computer Science notes cover the other chapters of this book, Class 12 notes hold every subject, and CBSE notes is the general index. For the data chapters that sit near this one, see understanding data, and for the parallel subject, Class 12 Informatics Practices notes.

Sources and data verification

What follows is plain information about where this page’s facts come from:

• The tables, programs and page numbers on this page describe NCERT Computer Science (Class XII), current official edition, Chapter 6: Searching.
• This page covers Chapter 6 only — not the other chapters of the Class 12 Computer Science book, and not the Informatics Practices book.
• The listing is maintained for the current academic session using NCERT’s published textbook; check NCERT’s site for any revised edition.
• NCERT settles textbook content, editions and the official PDF. CBSE settles the examinable syllabus, and textbook contents and the syllabus are not always identical — check the current official syllabus for what is examinable.

Frequently asked questions about Chapter 6 Searching

Why does binary search give wrong results on an unsorted list?

Binary search assumes the list is ordered. It compares the key with the middle element and throws away one half of the list as impossible — a valid move only when the elements are sorted.

The chapter’s second run of Program 6-2 shows the failure: the list [12, 8, 3] is entered out of order, and searching for 4 reports “not found” (NCERT, p. 9). Sort the list before applying binary search.

Why does the binary search program shrink the search area with mid – 1 and mid + 1 instead of mid?

The middle element has already been compared and did not match the key. The only remaining possibilities are before it or after it, so the next search area starts at mid + 1 or ends at mid − 1.

Reusing mid would re-compare an element already ruled out. The loop runs while first is less than or equal to last, and when first passes last the search is over (Algorithm 6.2, NCERT, p. 7).

Is hashing always faster than binary search?

Not always. Hashing gives a single, constant comparison when the key sits at the slot its hash function assigns — the time taken does not depend on the number of items in the list (NCERT, p. 10).

But the hash function’s own cost must stay small (NCERT, p. 12), and a collision can leave the key undiscoverable without collision resolution. Binary search is deterministic and needs no extra table, but takes about \( \log_2(n) \) iterations on a sorted list.

Why does the linear search program return position but the binary search program return index?

Both programs ultimately report a position, and both rely on position = index + 1. Program 6-1 adds 1 inside the function (return index+1); Program 6-2 returns the raw index and the main code prints pos+1 (NCERT, pp. 4, 9).

So “position 3” always means index 2.

What is a collision in hashing and why does the chapter not explain how to resolve it?

A collision happens when two elements produce the same hash value — the chapter’s example is 16 and 26 both giving 6 with element % 10 — so both cannot occupy the same slot (NCERT, p. 12).

Placing the later item elsewhere is collision resolution, but the chapter states the methods are beyond its scope (NCERT, p. 12). Know the definitions of collision and collision resolution; implementing resolution is not part of this chapter.

Reference: NCERT Class 12 Computer Science textbook, chapter 6, official edition on ncert.nic.in.