These searching class 12 notes condense NCERT Class 12 Computer Science Chapter 6 into a revision-ready page: the three search techniques — linear search, binary search and search by hashing — with trace tables, the chapter’s two formulas, and the mistakes students most often make while dry-running them.
The notes follow the 2026-27 session and the rationalised NCERT textbook; page references in brackets point back to the book.
Revise in this order: read the three technique sections, work the Worked Examples traces yourself, check your answers against the Textbook Activities table, then finish with the Revision Recap and FAQs. The full textbook, including Chapter 6, is available on the official NCERT textbook portal.
Searching Class 12: What Chapter 6 Covers
The chapter builds one idea on top of another, so revise it in teaching order rather than book order.
- Why searching matters. A computer stores data to retrieve it later. Searching means locating a particular element in a collection; the result tells you whether the element is present and, if it is, its position. The element you hunt for is called the key (NCERT, p. 81).
- Linear search — compare every element, one by one, until the key is found or the list ends. Works on small or unsorted lists (NCERT, p. 82).
- Binary search — repeatedly halve a sorted list and compare the key with the middle element (NCERT, p. 85).
- Search by hashing — compute the key’s position with a formula, so a search costs a single comparison (NCERT, p. 90).
Which one do you use? The one-line answer the chapter builds towards: unsorted or small → linear; sorted → binary; repeated lookups with a pre-built table → hashing.
The chapter’s binary-search section closes with its real-world reach — dictionary and telephone-directory lookups, finding the minimum or maximum value in a sorted list, and, in modified form, database indexing, routing tables in routers and data compression (NCERT, p. 90).
This page sits inside the Class 12 Computer Science notes hub; if you are preparing across subjects, start from the Class 12 notes collection.
Linear Search: Comparing Every Element
Linear search — also called sequential or serial search — compares every element of the list, one by one starting at index 0, with the key. The search is successful when an element matches; it is unsuccessful when the whole list is checked without a match (NCERT, pp. 82-83).
Because it never skips or reorders elements, it is one of the techniques that works on an unsorted list; hashing does too.
Algorithm 6.1 behaves like this: start index at 0; while index is still inside the list, compare list[index] with the key; on a match, print the key’s position as index + 1 and stop; otherwise move to the next index. If the loop finishes without a match, print “Search unsuccessful” (NCERT, p. 82).
The program version (Program 6-1) returns index + 1 when the key is found and None when it is absent (NCERT, p. 84).
How many comparisons it makes depends entirely on where the key sits:
- Key is the first element — exactly 1 comparison. This is the minimum work linear search can do (NCERT, p. 83).
- Key is anywhere in the middle — one comparison for each element before it, plus the matching one.
- Key is the last element, or is absent — all n elements are compared, so n comparisons. This is the maximum work (NCERT, pp. 83-84).
Notice the index versus position distinction that runs through this chapter: an element at index 3 is reported as position 4 (index + 1).
Binary Search: Halving a Sorted List
The book opens with a dictionary trick: to find Zoology you open the second half, because dictionary words are in alphabetical order (NCERT, p. 85). Binary search applies the same logic to any sorted list. The prerequisite is non-negotiable: the list must be sorted — ascending or descending for numbers, alphabetical for text (NCERT, p. 85).
Each iteration compares the key with the middle element of the current search window, and one of three things happens (NCERT, pp. 86-87):
- The middle element matches the key → search successful, stop.
- The middle element is greater than the key → the key must lie in the first half, so set last = mid – 1.
- The middle element is smaller than the key → the key lies in the second half, so set first = mid + 1.
The engine of the technique is the midpoint formula: mid = (first + last) // 2 (Algorithm 6.2, NCERT, p. 87). The // is Python’s floor division — it always produces a whole number, which a list index must be. The book’s even-element rule: for 10 elements, mid = 10 // 2 = 5, so the sixth element (index 5) is treated as the middle; if the search continues, the halves hold 5 and 4 elements (NCERT, p. 86).
Here is the chapter’s central insight: even a failed comparison teaches you something. It reveals which half of the list cannot contain the key, so each unsuccessful comparison halves the number of elements still to be searched. That repeated halving is exactly why it is called binary search (NCERT, p. 86).
The book therefore counts iterations, not comparisons, because after every unsuccessful comparison the search window (first, mid, last) is redefined before the next comparison is made (NCERT, p. 86).
Repeated halving continues until the key is found or only one element remains; if that last element is not the key, the search is unsuccessful (NCERT, p. 93). Program 6-2 returns the index of the key (and -1 when absent), and the calling code prints pos + 1 — a different convention from Program 6-1, which returns index + 1 directly (NCERT, pp. 84, 89).
Applications listed in the chapter: searching a dictionary or telephone directory, and finding the minimum or maximum value in a sorted list; modified binary search techniques appear in database indexing, router routing tables and data compression (NCERT, p. 90).
If your list is not sorted, binary search cannot be applied — the Sorting notes for Class 12 cover the sorting step you would run first.
Search by Hashing: One Jump to the Key
Picture a corridor of 10 lockers numbered 0 to 9. Each student is assigned the locker matching the last digit of their roll number, so roll number 23 goes straight to locker 3. To check whose roll number ends in 3, you walk to locker 3 — one step, no searching.
That is the whole idea of hashing: compute the position directly instead of comparing elements, so finding a key costs a single comparison no matter how large the list is (NCERT, p. 90). The catch, as with shared last digits, is that two students may claim the same locker — that overlap is a collision.
The terms come in a fixed order (NCERT, pp. 90-93):
- Hash function — a formula that takes each element of a list and generates an index value for it (NCERT, p. 90).
- Remainder method — the simple hash function the book uses for numbers: divide the element by the size of the hash table; the remainder is the element’s index (NCERT, p. 90).
- Hash value — the remainder produced by the remainder method (NCERT, p. 90).
- Hash table — the new list that stores each element at its computed index. It is implemented as a Python list; empty slots hold None, and the table may be larger than the list you started with (NCERT, p. 90).
The working flow is insert first, then search: compute each element’s hash value and place it at that slot of the table; later, to search a key, compute its hash value, look at that one slot, and compare. One comparison decides presence or absence (NCERT, pp. 90-91).
If more than one element gives the same remainder — the Think and Reflect question on p. 90 — the elements collide, and since a slot holds one item, you need collision resolution to place the rest (NCERT, p. 92). The book explicitly keeps the resolution methods out of scope.
Two definitions close the section. A collision is the situation where two or more elements map to the same slot of the hash table because their hash values match (NCERT, p. 92) — for example, with table size 10, the elements 26 and 36 both leave remainder 6.
A perfect hash function maps every item to a unique index, so a collision can never occur (NCERT, p. 93). One honest caveat from the book: the time a hash function takes must stay small enough that hashing still beats the other search methods (NCERT, p. 93).
Inside the program, a hash table is just a Python list — revisit how lists are stored in the Understanding Data notes if that feels shaky.
Searching Glossary: Key Terms With Examples
One table of every exam-relevant term, with page references: key and searching (p. 81), linear search (p. 82), binary search and iteration (pp. 85-86), and the hashing terms (pp. 90-93).
| Term | Meaning | Example |
|---|---|---|
| Key | The value you are trying to locate in the collection. | In “search for 23 in [12, 45, 7, 23, 8, 19]”, the key is 23. |
| Searching | Locating a particular element in a collection; the result says whether it is present and, if so, its position. | Checking whether 8 is in [5, 8, 2] finds it at position 2. |
| Linear search | The simplest search: compare every element from the start until the key is found or the list ends; also called sequential or serial search. | [12, 45, 7, 23, 8, 19] with key 23 takes 4 comparisons; the key sits at position 4. |
| Binary search | A search on a sorted list that compares the key with the middle element and discards the half that cannot contain the key. | Key 40 in the sorted list [4, 9, 15, 22, 31, 40, 56] is found in 2 iterations. |
| Iteration | One pass of the search loop, in which the search window (first, mid, last) may be redefined; binary search counts iterations rather than comparisons. | Searching key 2 in a 15-element sorted list needs 4 iterations. |
| Sorted list | A list arranged in order — ascending or descending for numbers, alphabetical for text. Required before binary search. | [4, 9, 15, 22, 31, 40, 56, 67, 78, 85] is sorted ascending. |
| Hash function | A formula that takes each element and generates an index value where the element will be stored. | The function \( \text{element} \% 10 \) stores 24 at index 4. |
| Remainder method | A numeric hash function: divide the element by the hash table size and keep the remainder as the hash value. | \( h(58) = 58\ \%\ 10 = 8 \). |
| Hash value | The remainder produced by the remainder method; it becomes the element’s storage index. | For the function above, 58’s hash value is 8. |
| Hash table | The list built by storing each element at its computed index; empty slots hold None and it can be bigger than the original list. | [90, 11, 42, 63, 24, None, None, 37, 58, None]. |
| Collision | The situation where two or more elements map to the same slot because their hash values match. | With table size 10, 26 and 36 both hash to 6. |
| Collision resolution | The process of placing the second and later items when a collision occurs; methods are beyond this book’s scope. | The chapter defines the term but implements no resolution method. |
| Perfect hash function | A hash function that maps every item to a unique index, so collisions can never happen. | If 7 items fill 7 distinct slots, the function is perfect for that data. |
Formulas in Searching: Midpoint and Hash Function
The chapter has exactly two formulas. Both produce an integer index, which is what a list position needs.
\[ \text{mid} = (\text{first} + \text{last})//2 \]
This is the binary search midpoint, computed with first = leftmost index of the current search window, last = rightmost index, and // as Python’s floor division, which rounds down to a whole number. With first = 4 and last = 9: \( \text{mid} = (4+9)//2 = 6 \) (NCERT, pp. 86-87).
\[ h(\text{element}) = \text{element}\ \%\ \text{size(hash table)} \]
This is the remainder-method hash function: element is one value from the list, size(hash table) is the number of slots, and the remainder of the division is the hash value — the index where the element is stored (NCERT, p. 90). With a 10-slot table: \( h(58) = 58\ \%\ 10 = 8 \), so 58 is stored at index 8.
Why floor division? If (first + last) is odd, ordinary division yields a fraction such as 4.5, and a Python list index cannot be a float. The // operator rounds down, so mid is always usable as list[mid] (NCERT, p. 86).
The chapter expresses cost in words rather than Big-O notation — repeated halving for binary search, one comparison regardless of size for hashing — so no complexity symbols are needed for this chapter.
Worked Examples: Tracing Linear, Binary and Hash Searches
All traces below obey one convention: indices are computed from 0, printed positions are 1-based (index + 1). Counts are stated at every step.
Example 1: Linear search — key present and key absent
Method: linear search, which compares from index 0 until a match or the end of the list.
Data: list = [12, 45, 7, 23, 8, 19], key = 23, n = 6.
- Compare index 0: is 12 = 23? No — move to index 1.
- Compare index 1: is 45 = 23? No — move to index 2.
- Compare index 2: is 7 = 23? No — move to index 3.
- Compare index 3: is 23 = 23? Yes — stop the search.
| index | comparison | match? | next index |
|---|---|---|---|
| 0 | 12 = 23? | No | 1 |
| 1 | 45 = 23? | No | 2 |
| 2 | 7 = 23? | No | 3 |
| 3 | 23 = 23? | Yes | stop — position = 3 + 1 = 4 |
Result: 4 comparisons; the key 23 is at index 3, printed as position 4 (“Element found at position 4”).
Absent-key variant: key = 99. Each of the 6 elements is compared (12, 45, 7, 23, 8, 19 — none equals 99), so the search makes 6 comparisons and ends unsuccessful. This is the n-comparison worst case, the same as when the key is the last element (NCERT, pp. 83-84).
Example 2: Binary search — 10-element sorted list
Method: binary search, which requires a sorted list and compares the key with mid each iteration, where \( \text{mid} = (\text{first} + \text{last})//2 \).
Data: sorted list = [4, 9, 15, 22, 31, 40, 56, 67, 78, 85], key = 40, n = 10.
- Iteration 1: first = 0, last = 9, so \( \text{mid} = (0+9)//2 = 4 \). numList[4] = 31. Since 40 is greater than 31, the key lies in the second half → first = mid + 1 = 5.
- Iteration 2: first = 5, last = 9, so \( \text{mid} = (5+9)//2 = 7 \). numList[7] = 67. Since 40 is smaller than 67, the key lies in the first half → last = mid – 1 = 6.
- Iteration 3: first = 5, last = 6, so \( \text{mid} = (5+6)//2 = 5 \). numList[5] = 40 — match. Stop.
| Iteration | first | last | mid = (first+last)//2 | numList[mid] | comparison | action |
|---|---|---|---|---|---|---|
| 1 | 0 | 9 | (0+9)//2 = 4 | 31 | 40 greater than 31 | first = 5 |
| 2 | 5 | 9 | (5+9)//2 = 7 | 67 | 40 smaller than 67 | last = 6 |
| 3 | 5 | 6 | (5+6)//2 = 5 | 40 | 40 equals 40 | stop — found |
Result: 3 iterations; the key 40 is at index 5, printed as position 6 (mid + 1 = 6). Notice the even-list behaviour: with 10 elements the first window runs from 0 to 9, and floor division keeps mid an integer at every step (NCERT, p. 86 for the rule).
Example 3: Search by hashing — 7 elements in a 10-slot table
Method: remainder-method hashing with table size 10, so \( h(\text{element}) = \text{element}\ \%\ 10 \).
Data: list = [24, 37, 11, 58, 63, 42, 90].
- Compute each element’s hash value: \( 24\ \%\ 10 = 4 \), \( 37\ \%\ 10 = 7 \), \( 11\ \%\ 10 = 1 \), \( 58\ \%\ 10 = 8 \), \( 63\ \%\ 10 = 3 \), \( 42\ \%\ 10 = 2 \), \( 90\ \%\ 10 = 0 \).
- Insert each element at its computed slot to build the hash table.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| value | 90 | 11 | 42 | 63 | 24 | None | None | 37 | 58 | None |
Search present key 63: \( 63\ \%\ 10 = 3 \). Slot 3 holds 63 — match. One comparison; position = 3 + 1 = 4, so 63 is reported as present at position 4.
Search absent key 55: \( 55\ \%\ 10 = 5 \). Slot 5 holds None — no match. One comparison; 55 is declared not present in the table.
Result: each hash search costs exactly 1 comparison, present or absent — the property that makes hashing independent of list size (NCERT, pp. 90-91).
Common Mistakes in Searching and Their Fixes
| Students write or do this… | Correct is… | Why, and how to check your answer |
|---|---|---|
| Running binary search on an unsorted list. | Sort the list first (list.sort()) before searching, or use linear search on the unsorted data. | Binary search’s midpoint comparison only makes sense when the list is ordered; on unsorted data it can discard the half that actually contains the key (NCERT, pp. 85-86). Check: print the list after sorting. |
| Computing mid with a single slash: mid = (first + last) / 2. | Use floor division: mid = (first + last) // 2. | In Python, / returns a float and a list index must be an integer — list[mid] would crash. The even-element rule also assumes floor division (NCERT, p. 86). Check: mid always comes out a whole number. |
| Updating first = mid (or last = mid) instead of mid ± 1. | Larger key → first = mid + 1; smaller key → last = mid – 1 (Algorithm 6.2). | If mid stays inside the new window, the search area never shrinks and the loop never ends (NCERT, p. 87). Check: trace two iterations — first must move past mid, or last must move before it. |
| Mixing up index and position between the two programs. | Program 6-1 returns index + 1 (the position). Program 6-2 returns the raw index, and the caller prints pos + 1. | A 0 returned by Program 6-2 means “index 0, the first element”, while Program 6-1 would have returned 1; a -1 from Program 6-2 means “not found”. Confusing the two causes off-by-one errors (NCERT, pp. 84, 89). |
| Assuming linear search reports every duplicate. | Linear search stops and returns at the first match only. | The function returns the moment an element equals the key, so later copies are never examined — in [42, -2, 32, 8, 17, 19, 42, 13, 8, 44], key 8 returns the first 8 at position 4, never the second (NCERT, p. 84; Exercise Q2, p. 94). |
| Treating a collision as a broken hash function. | Collision is expected in hashing; collision resolution is the separate step that handles it. | The book defines collision and resolution but keeps resolution methods out of scope, so a complete answer names the collision and moves on (NCERT, p. 92). |
| Searching the hash table before it is built — or forgetting that the naive insert overwrites collided values. | Build the full hash table before any search; remember Program 6-3 inserts with a plain assignment (hashTable[element % 10] = element). | If two keys share a slot, the later assignment replaces the earlier value, so a search for the overwritten key fails even though the key was in the original list (NCERT, pp. 91-92). Check: insert each element slot by slot before declaring any search result. |
Answering the NCERT Exercise Questions: What a Complete Answer Needs
These pointers shape complete answers to the exercises on NCERT pp. 94-96 — they are guidance, not the worked solutions.
- Q1 (linear-search trace, p. 94): reproduce the book’s trace-table form — columns index | index < n | numList[index] == key | index = index+1 — one row per pass, for each of the four keys 8, 1, 99 and 44. State the printed position for found keys and “unsuccessful” for the absent one. The table is the answer, so every column must be filled for every pass.
- Q2 (duplicates, p. 94): state that the returned position is the first occurrence. In [42, -2, 32, 8, 17, 19, 42, 13, 8, 44], key 8 is found at position 4 — the second 8 at position 9 is never reached because the function returns on the first match. The “what does this mean” half of the answer should say: the program reports whichever copy appears first.
- Q3, Q4 and Q6 (programs, pp. 94-95): a complete program answer has five parts — define the search function (linearSearch or binarySearch as in the chapter), build the input list, call the function with a key, print the position or a not-found message, and run it for at least 3 different keys, noting each result. Q6 adds word lists (so linear vs binary on text strings), but the structure is identical.
- Q7 (large-database estimate, p. 96): the record sits at the middle of \( 2^{30} \) (1,073,741,824) sorted records. Binary search compares the middle record first, so it needs 1 iteration. Linear search walks from the start to the middle, comparing roughly half the records — about \( 2^{29} + 1 \) comparisons. The interpretation the answer should carry: on a large sorted database, binary search is overwhelmingly faster; the sorted requirement is the price of that speed.
- Q8 (hash table, p. 96): build the table with \( h(\text{element}) = \text{element}\ \%\ 11 \). The insight the book never states: every number given — 44, 121, 55, 33, 110, 77, 22, 66 — is a multiple of 11, so every remainder is 0, and every element hashes to index 0. With the chapter’s naive insert, each later value overwrites the previous one, so only the last element survives in slot 0. A complete answer still displays the 11-slot table and reports the search results for 11, 44, 88 and 121 as asked — but the conceptual note worth adding is that this table cannot hold more than one distinct value because h gives every element the same index: every pair of elements collides.
- Q9 (countries and capitals, p. 96): the hash index comes from the country name’s length: \( \text{hash index} = \text{length(country)} – 1 \). India (5 letters) goes to index 4, with New Delhi in the matching slot of the values list. Searching for the capital of the USA means computing \( \text{len(‘USA’)} – 1 = 2 \) and checking the keys list at index 2 — which holds None — so the answer is “not found”. For every search, state both the index computed and the value found at it.
Textbook Activities 6.1 to 6.5: Check Your Dry Run
Dry-run the activities yourself first, then compare against this table. The numbers come from tracing the book’s own lists.
| Activity | What it asks | Result of the dry run |
|---|---|---|
| 6.1 (p. 82) | Number of comparisons to find key 12 in the 15-element list [2, 3, 9, 7, -6, 11, 12, 17, 45, 23, 29, 31, -37, 41, 43]. | 7 comparisons — key 12 sits at index 6, so six comparisons fail and the seventh matches. |
| 6.2 (p. 83) | Number of comparisons to find key 43 in [7, -1, 11, 32, 17, 19, 23, 29, 31, 37, 43]. | 11 comparisons — 43 is the last of the 11 elements, so this is the n-comparison worst case. |
| 6.3 (p. 86) | Sort [17, 8, -4, 7, 0, 2, 19] with list.sort(), then binary-search for key 7. | 1 iteration — after sorting, 7 is exactly the middle element (index 3) of [-4, 0, 2, 7, 8, 17, 19]. |
| 6.4 (p. 86) | Binary search for key -4 in [-4, 0, 2, 7, 8, 17, 19]; count the key comparisons. | 3 comparisons — mid index 3 (value 7) → index 1 (value 0) → index 0 (value -4, match). |
| 6.5 (p. 88) | Fill the Table 6.8 iteration counts for keys 2, 43, 17 and 9 in the 15-element sorted list [2, 3, 5, 7, 10, 11, 12, 17, 19, 23, 29, 31, 37, 41, 43]. | Key 2 → 4 iterations; key 43 → 4 iterations; key 17 → 1 iteration; key 9 → 4 iterations (unsuccessful). |
Inference the book wants from Activity 6.5: a key at the middle costs 1 iteration, while extreme keys (2, 43) or a missing key (9) cost the maximum — 4 iterations for a 15-element list.
Searching at a Glance: Revision Recap
The whole chapter on one screen:
| Method | Needs a sorted list? | Best case | Worst case | Typical use |
|---|---|---|---|---|
| Linear search | No | 1 comparison — key at the first position (NCERT, p. 83) | n comparisons — key last or absent (NCERT, pp. 83-84) | Small or unsorted lists (NCERT, p. 82) |
| Binary search | Yes | 1 iteration — key is the middle element (NCERT, p. 87) | Repeated halving until one element remains — about the number of times n halves down to 1 (a 15-element list needs at most 4 iterations, NCERT, p. 88) | Sorted data; dictionary and telephone-directory lookups (NCERT, p. 90) |
| Hashing | No — but the hash table must be built first | 1 comparison | 1 comparison | Repeated lookups when the hash computation stays cheap (NCERT, p. 93) |
The three-line decision rule: list unsorted or tiny → linear search; list sorted → binary search; repeated lookups with the table built once → hashing.
Two memory devices. For choosing a method: “Linear looks one by one, binary bisects half by half, hashing hops straight to the slot.”
For the binary-search pointer updates: a larger key jumps first up past mid (first = mid + 1), a smaller key pulls last down past mid (last = mid – 1) — forget the plus or minus one and the window never shrinks, so the loop never ends.
For quick access to every chapter in this book and other subjects, browse the complete notes library on LearnCBSE.
Frequently Asked Questions: Searching Class 12
What is the difference between linear search and binary search?
Linear search compares every element from the start until the key is found, so it works on unsorted lists but can take up to n comparisons.
Binary search compares the key with the middle element of a sorted list and discards half the remaining elements after each comparison, so it is far faster on large sorted data — the condition is that the list must be sorted first (NCERT, pp. 82, 85-86).
Can binary search be used on an unsorted list?
No. Binary search decides whether the key lies in the first or second half by comparing it with the middle element — that decision is only valid if the list is ordered (NCERT, p. 85). On an unsorted list the algorithm can skip past the key. Apply list.sort() before binary search, or use linear search on the raw list (NCERT, pp. 85-86).
What is a collision in hashing and how is it resolved?
A collision occurs when two elements produce the same hash value, so both map to the same slot of the hash table, and a slot can hold only one item (NCERT, p. 92). Placing the later items is called collision resolution. The chapter defines both terms but leaves the resolution methods out of scope (NCERT, p. 92).
If a list has duplicate values, which position does linear search return?
The first occurrence. The function returns as soon as an element equals the key, so duplicates later in the list are never examined. In [42, -2, 32, 8, 17, 19, 42, 13, 8, 44], searching for 8 returns the first 8 at position 4, not the second 8 at position 9 (NCERT, p. 84; Exercise Q2, p. 94).
Why is mid calculated with floor division in binary search?
So that mid is always a whole number and can be used as a list index. When the window holds an even number of elements, (first + last) is odd and ordinary division gives a fraction; // rounds down. The book’s even-element rule states that for 10 elements mid = 10 // 2 = 5, making the sixth element (index 5) the middle (NCERT, p. 86).
How many comparisons does hashing require to find a key?
Exactly one — as long as the hash table is built and the hash function maps the key to its slot. You compute the key’s index, inspect that one slot, and declare the key present or absent. The count stays one regardless of list size, provided the hash computation itself stays cheap (NCERT, pp. 90-91, 93).
Reference: NCERT Class 12 Computer Science textbook, chapter Searching.
Explore Class 12 Computer Science Notes
- Class 12 Computer Science Notes
- Class 12 CBSE Notes
- CBSE Notes for Classes 1 to 12
- Previous: Sorting
- Next: Understanding Data
Class 12 Computer Science on LearnCBSE:
Related chapters:
- File Handling in Python notes
- Queue notes
- Database Concepts notes