Complete Summary and Solutions for Searching – NCERT Class XII Computer Science, Chapter 6 – Linear Search, Binary Search, Hashing, Algorithms, Questions, Answers

Comprehensive summary and explanation of Chapter 6 'Searching' from the Computer Science textbook for Class XII, covering the concept of searching, linear search algorithm and its working, binary search algorithm for sorted lists, hashing techniques for efficient search, collision, and collision resolution—along with all NCERT questions, answers, and exercises for practical understanding.

Updated: 4 months ago

Categories: NCERT, Class XII, Computer Science, Chapter 6, Searching, Linear Search, Binary Search, Hashing, Summary, Questions, Answers, Programming, Comprehension

Tags: Searching, Linear Search, Binary Search, Hashing, Collision, Algorithms, NCERT, Class 12, Computer Science, Summary, Explanation, Questions, Answers, Programming, Chapter 6

Searching in Python - Class 12 Computer Science Chapter 6 Ultimate Study Guide 2025

Full Chapter Summary & Detailed Notes - Searching Class 12 NCERT

Overview & Key Concepts

Chapter Goal: Understand searching techniques: Linear (sequential), Binary (divide-conquer on sorted), Hashing (direct access via function). Exam Focus: Algorithms 6.1-6.2, Programs 6-1 to 6-3, Tables 6.1-6.10; 2025 Updates: Efficiency in big data. Fun Fact: Brian Kernighan quote on computing ties to search ops. Core Idea: Efficient retrieval from collections; from O(n) linear to O(1) hash. Real-World: Database queries. Expanded: All subtopics point-wise with evidence (e.g., Table 6.2 comparisons), examples (e.g., key=17 in [8,-4,7,17...]), debates (e.g., sorted cost vs binary speed).
Wider Scope: From unsorted small lists to hashed tables; sources: Algorithms, programs, tables/figures.
Expanded Content: Include time complexity (linear O(n), binary O(log n), hash O(1)); point-wise for recall; add 2025 relevance like parallel search.

Introduction

Searching Defined: Locate key in collection; return presence/position. Essential for data retrieval.
Importance: Algorithms need varied search methods; affects efficiency.
Example: Home items vs computer data on demand.
Practical Difficulties: Unordered → slow; Solutions: Choose method by list size/order.
Expanded: Evidence: Quote on computing impact; debates: Search vs sort trade-off; real: Search engines.

Conceptual Diagram: Search Flow

Flow: Collection → Key Input → Compare/Compute Index → Found/Not Found → Position/None. Ties to Algorithm 6.1.

Why This Guide Stands Out

Comprehensive: All methods point-wise, program integrations; 2025 with big-O analysis, processes for real code.

Linear Search

Overview: Sequential check from start; O(n) worst/best variable. For small/unsorted lists.
Algorithm 6.1: Index=0; while
Example 6.1: [8,-4,7,17,0,2,19] key=17 → 4 comparisons (Table 6.2).
Best/Worst: First elem (1 comp), last/not found (n comps) (Tables 6.3-6.4).
Program 6-1: Input list/key; return pos/None (Output: 23 at 2).
Expanded: Evidence: Activity 6.1 (key=12 → 8 comps); real: Unsorted arrays.

Index	Value
0	8
1	-4
2	7
3	17

Binary Search

Overview: Divide sorted list; compare mid; halve search. O(log n).
Pre-req: Sorted ascending/descending/alphabetical.
Process: Mid=(first+last)//2; if match return; >key last=mid-1;
Example 6.2: [2,3,5,7,10,11,12,17...] key=17 → 1 iter (mid=7, match Table 6.6).
Max Iter: Key=2 → 4 iters (Table 6.7, halves 15→7→3→1).
Program 6-2: Input sorted list/key; return index/-1 (Output: 4 at 3; not found).
Expanded: Evidence: Activity 6.3 (key=7 → 2 iters); debates: Sort overhead.

Search by Hashing

Overview: Hash function → index; O(1) lookup. Hash table > list size possible.
Hash Function: Remainder (elem % size); e.g., %10.
Example: List [34,16,2,93,80,77,51] → Table 6.10 (80 at 0, etc.).
Search: Compute index; compare once (Program 6-3, Output: 16 at 7).
Collision: Same hash (e.g., 16%10=6, 26%10=6); resolve beyond scope.
Expanded: Evidence: Perfect hash no collision; real: Dictionaries.

Summary & Exercise

Key Takeaways: Linear simple/slow; Binary fast/sorted; Hash constant/direct. Choose by scenario.
Exercise Tease: Compare comps (Ex1: positions); code linear/binary (Ex3-4); hash table (Ex8).

Key Definitions & Terms - Complete Glossary

All terms from chapter; detailed with examples, relevance. Expanded: 25+ terms grouped by subtopic; added advanced like "Time Complexity", "Collision Resolution" for depth/easy flashcards.

Searching

Locate key in collection. Ex: Find 17 in list. Relevance: Data retrieval.

Linear Search

Sequential from start. Ex: Algorithm 6.1. Relevance: Unsorted small lists.

Binary Search

Halve sorted list. Ex: Algorithm 6.2. Relevance: Efficient on ordered data.

Hashing

Function to index. Ex: %10. Relevance: Constant time access.

Key

Item to search. Ex: 17. Relevance: Target element.

Hash Table

Array for hashed values. Ex: Table 6.10. Relevance: Storage structure.

Hash Function

Compute index. Ex: Remainder method. Relevance: Mapping tool.

Collision

Same hash value. Ex: 16 and 26 %10=6. Relevance: Resolution needed.

Perfect Hash

No collisions. Ex: Unique mappings. Relevance: Ideal efficiency.

Sorted List

Ordered ascending/desc. Ex: [2,3,5...]. Relevance: Binary pre-req.

Mid Position

(first+last)//2. Ex: 10 elems → index 5. Relevance: Binary pivot.

Sequential Search

Another name for linear. Ex: Item-by-item. Relevance: Simple impl.

Time Complexity

Operations count. Ex: Linear O(n). Relevance: Efficiency measure.

O(1)

Constant time. Ex: Hash lookup. Relevance: Best case.

O(n)

Linear time. Ex: Linear search worst. Relevance: Scales with size.

O(log n)

Logarithmic. Ex: Binary iters. Relevance: Efficient scaling.

Iteration (Binary)

Halving step. Ex: 4 iters for 15 elems. Relevance: Not direct comps.

Comparison

Key vs element. Ex: Linear 4 for key=17. Relevance: Work measure.

Unsuccessful Search

Key not found. Ex: Print "unsuccessful". Relevance: n comps linear.

Successful Search

Key found. Ex: Position 4. Relevance: Early stop possible.

Tip: Group by method; examples for recall. Depth: Debates (e.g., hash collisions). Historical: Binary in dictionaries. Interlinks: To sorting Ch5. Advanced: Chaining resolution. Real-Life: Google search. Graphs: Complexity table. Coherent: Evidence → Interpretation. For easy learning: Flashcard per term with table ex.

60+ Questions & Answers - NCERT Based (Class 12) - From Exercises & Variations

Based on chapter + expansions (Ex1-9 p94-96). Part A: 10 (1 mark, one line), Part B: 10 (3 marks, four lines), Part C: 10 (4 marks, six lines), Part D: 10 (6 marks, eight lines). Answers point-wise in black text. Include code/tables where apt.

Part A: 1 Mark Questions (10 Qs - Short)

1. Define searching.

1 Mark Answer:

Locate key in collection.

2. What is linear search?

1 Mark Answer:

Sequential comparison.

3. Pre-req for binary search?

1 Mark Answer:

Sorted list.

4. Hash function example?

1 Mark Answer:

Element % size.

5. What is collision?

1 Mark Answer:

Same hash value.

6. Linear worst case?

1 Mark Answer:

n comparisons.

7. Binary mid calc?

1 Mark Answer:

(first+last)//2.

8. Hash time complexity?

1 Mark Answer:

O(1).

9. Perfect hash?

1 Mark Answer:

No collisions.

10. Binary for even elems?

1 Mark Answer:

Floor division.

Part B: 3 Marks Questions (10 Qs - Medium, Exactly 4 Lines Each)

1. Differentiate linear vs binary.

3 Marks Answer:

Linear: Unsorted, O(n).
Binary: Sorted, O(log n).
Ex: Linear 4 comps; binary 1 iter.
Linear simple; binary efficient.

2. Steps in Algorithm 6.1.

3 Marks Answer:

Index=0; while
If match: Print pos.
Else index++.
End: Unsuccessful.

3. Why binary halves list?

3 Marks Answer:

Mid > key: Ignore right.
Mid < key: Ignore left.
Ex: 15→7→3→1.
Reduces search area.

4. Hash function remainder method.

3 Marks Answer:

h(elem) = elem % size.
Ex: 34%10=4.
Insert at index.
One comp search.

5. Linear for duplicates.

3 Marks Answer:

Returns first pos.
Ex: [...,8,...,8] → first 8.
Continues till match.
Ex2: Key not found n comps.

6. Binary applications.

3 Marks Answer:

Dictionary/telephone dir.
Min/max in sorted.
DB indexing.
Data compression.

7. Collision in hashing.

3 Marks Answer:

Same remainder.
Ex: 16,26 %10=6.
Resolution needed.
Beyond scope.

8. Linear comps for key=43.

3 Marks Answer:

List ends with 43.
n=11 comps.
Worst case.
Table trace.

9. Binary for even list.

3 Marks Answer:

10 elems: mid=5 (6th elem).
First half 5, second 4.
Floor //.
Continue halving.

10. Hash table size.

3 Marks Answer:

> List size possible.
Ex: 10 slots for 7 elems.
Reduces collisions.
Python list impl.

Part C: 4 Marks Questions (10 Qs - Medium-Long, Exactly 6 Lines Each)

1. Explain linear with Ex6.1.

4 Marks Answer:

Compare seq till match.
[8,-4,7,17...] key=17.
4 comps (Table 6.2).
Pos 4.
Best:1, worst:n.
Simple, no sort.

2. Binary process with Table 6.7.

4 Marks Answer:

Mid compare, halve.
Key=2: Iter1 mid=17>2 left.
Iter2 mid=7>2 left.
Iter3 mid=3>2 left.
Iter4 match pos1.
Max log n iters.

4. Hash table creation Ex Table 6.10.

4 Marks Answer:

%10 on [34,16...51].
34→4, 16→6, etc.
Table: 0=80,1=51,...
Search: key%10 compare.
One step.
Collisions possible.

5. Compare linear/binary comps (Activity 6.5).

4 Marks Answer:

List 15 elems.
Linear key2:15,43:15,17:8,9:15.
Binary:2:4,43:4,17:1,9:4.
Binary fewer iters.
Linear consistent worst.
Binary log efficient.

6. Program 6-1 linear code.

4 Marks Answer:

Def linearSearch: for loop if match return pos.
Input list size, elems.
Key input, call func.
Print pos/None.
Output ex:23 at2.
Handles not found.

7. Binary vs linear performance.

4 Marks Answer:

Linear: Small unsorted.
Binary: Large sorted, faster.
Ex: 2^30 records mid:30 iters linear 2^30.
Binary scales log.
Sort cost amortize.
Hash beats both avg.

8. Hash collisions resolution.

4 Marks Answer:

Multiple at slot.
Ex: Chaining lists.
Open addressing probe.
Beyond book.
Perfect hash avoid.
Larger table help.

9. Unsorted to sorted linear/binary (Ex5).

4 Marks Answer:

Unsorted linear:1=24,5=24,55=24,99=24 comps.
Sort asc.
Sorted linear same 24.
Binary:1=5,5=3,55=4,99=5 iters.
Binary faster.
Sort enables.

10. Hash for words (Ex6 var).

4 Marks Answer:

Linear unsorted: Amazing=16,Perfect=1,Great=5,Wondrous=8 comps.
Sort alpha.
Sorted linear same.
Binary: Amazing=4,Wondrous=16 iters? Wait log16=4.
Words alphabetical.
Binary efficient.

Part D: 6 Marks Questions (10 Qs - Long, Exactly 8 Lines Each)

1. Trace linear for [1,-2,32,8...] keys 8,1,99,44 (Ex1).

6 Marks Answer:

List 10 elems.
Key8:4 comps pos4.
Key1:1 comp pos1.
Key99:10 comps not.
Key44:10 comps pos10.
Table: Index,val,decision.
Worst for absent/end.
Linear exhaustive.

2. Linear duplicates [42,-2,32,8...] key=8 (Ex2).

6 Marks Answer:

Returns first pos4.
Second 8 at9 ignored.
Stops at match.
Means first occurrence.
Ex output: Pos4.
For all: Modify continue.
Useful unique.
Program trace.

3. Code linear mix neg/pos + key (Ex3).

6 Marks Answer:

Input 10 nums list.
Key int.
Linear func return pos/None.
Print present/not +pos.
Run keys: Found pos, not msg.
Ex: [ -5,3...] key3 pos2.
Handles neg.
3 runs evidence.

# Similar to Prog 6-1
def linear(lst, k): for i in range(len(lst)): if lst[i]==k: return i+1
return None
# Input loop, call, print

4. Code binary 10 ints + key (Ex4).

6 Marks Answer:

Input 10 nums asc.
Assume sorted or sort().
Binary func first/last/mid.
Return index/-1.
Print pos/not.
Run 3 keys: Found/not.
Ex: [1,2..10] key5 pos5.
Evidence outputs.

# Like Prog 6-2
def bin_search(lst, k): # while first<=last mid=... return mid or -1

5. Ex5 full: Linear unsort/sort + binary (p95).

6 Marks Answer:

Unsorted linear: All 24 comps.
sort(lst).
Sorted linear still 24.
Binary: log24≈5 iters each.
Ex key1:5 iters pos1.
Binary superior post-sort.
Trade sort time.
Record tables.

6. Ex6 words linear/sort/binary.

6 Marks Answer:

Unsorted linear: Positions vary comps.

sort() alpha.

Sorted linear same comps.

Binary: 4 iters avg log16.

Ex Amazing pos1:1 iter.

Words suit binary.

Record iters.

Efficiency gain.

7. Binary/linear for 2^30 records mid (Ex7).

6 Marks Answer:

Mid pos: Linear 2^30/2 ≈5e8 comps.
Binary: log2(2^30)=30 iters.
Huge diff.
Interpret: Binary scales; linear impractical large.
Real DB use binary.
Evidence calc.
Hash even better.
Choose wisely.

8. Hash h=elem%11 for [44,121...] search 11,44,88,121 (Ex8).

6 Marks Answer:

Table:44%11=0,121%11=0 collision,55%11=0,...
Display table with collisions.
Search:11%11=0 check, not;44=0 yes;88%11=0 no;121=0 yes.
Collisions issue.
Ex table row.
One comp each.
Resolution hint.
Program sim.

9. Hash countries capitals len(key)-1 (Ex9).

6 Marks Answer:

Dict to lists keys/values.
Hash=len(country)-1.
India=5-1=4: keys[4]=India vals[4]=New Delhi.
UK=2-1=1, France=6-1=5 collision? Wait unique.
Search India: len=5 idx4 match.
France idx5, USA len=3 idx2 None.
Display results.
Word hashing.

10. Compare all methods efficiency.

6 Marks Answer:

Linear: Easy O(n) unsorted.
Binary: Sort + O(log n) ordered.
Hash: O(1) but collisions.
Ex 1000 elems: Linear1000, binary10, hash1.
Choose: Small linear, large binary/hash.
2025: Big data hash.
Trade-offs.
Programs evidence.

Tip: Include tables/code in ans; practice trace. Additional 30 Qs: Variations on activities, comps.

Key Concepts - In-Depth Exploration

Core ideas with examples, pitfalls, interlinks. Expanded: All concepts with steps/examples/pitfalls for easy learning. Depth: Debates, analysis.

Linear Search

Steps: 1. Start index0, 2. Compare till match/end. Ex: Table6.2. Pitfall: Slow large lists. Interlink: Base for others. Depth: Variable best/worst.

Binary Search

Steps: 1. Sort, 2. Mid compare, 3. Halve. Ex: Table6.7. Pitfall: Unsorted fail. Interlink: Sorting Ch5. Depth: Log efficiency.

Hashing

Steps: 1. Compute hash, 2. Insert/lookup. Ex: Table6.10. Pitfall: Collisions degrade. Interlink: Dicts Ch4. Depth: O(1) avg.

Time Complexity

Steps: 1. Count ops, 2. Big-O. Ex: Linear O(n). Pitfall: Ignore constants. Interlink: Analysis. Depth: Asymptotic.

Sorted Requirement

Steps: 1. Asc/desc order. Ex: Dictionary words. Pitfall: Wrong order wrong result. Interlink: Binary. Depth: Alphabetical numeric.

Mid Calculation

Steps: //2 floor. Ex: Even 10→5. Pitfall: Overflow large n. Interlink: Binary. Depth: Balances halves.

Collisions

Steps: 1. Detect same hash, 2. Resolve. Ex: %10=6 twice. Pitfall: Degrades to linear. Interlink: Hash. Depth: Chaining/probing.

Unsuccessful Search

Steps: Traverse full. Ex: Key10 not in list n comps. Pitfall: Same as worst success. Interlink: Linear. Depth: Always n linear.

Hash Function

Steps: Map to index. Ex: Remainder. Pitfall: Poor dist collisions. Interlink: Perfect. Depth: Modulo variants.

Efficiency Trade-off

Steps: 1. Assess size/order, 2. Choose. Ex: Small linear, large binary. Pitfall: Wrong choice slow. Interlink: All. Depth: Amortized.

Iteration vs Comparison

Steps: Binary iter=halve+comp. Ex: 4 iters 3 comps. Pitfall: Confuse counts. Interlink: Binary. Depth: Log iters.

Sequential vs Divide

Steps: Linear seq, binary divide. Ex: Linear full scan. Pitfall: Linear no skip. Interlink: Methods. Depth: Conquer strategy.

Direct Access

Steps: Hash compute direct. Ex: O(1). Pitfall: Table size mem. Interlink: Hash. Depth: No traversal.

Perfect Hashing (Adv)

Steps: Unique map. Ex: No collision. Pitfall: Hard construct. Interlink: Hash. Depth: Static sets.

Advanced: Parallel binary, bloom filters. Pitfalls: Hash uniform. Interlinks: To stacks Ch3. Real: SQL indexes. Depth: 14 concepts details. Examples: Real tables. Graphs: Comp curves. Errors: Unsorted binary. Tips: Steps evidence; compare tables (linear vs binary comps).

Code Examples & Programs - From Text with Simple Explanations

Expanded with evidence, analysis; focus on applications. Added variations for practice.

Example 1: Linear Search (Program 6-1)

Simple Explanation: Seq check list.

def linearSearch(list, key):  
    for index in range(0,len(list)):
        if list[index] == key: 
            return index+1 
    return None  
list1 = [] 
maximum = int(input("How many elements? "))
for i in range(0,maximum):
    n = int(input())
    list1.append(n) 
key = int(input("Enter key: ")) 
position = linearSearch(list1, key)
if position is None:
    print("Not present")
else:
    print("At",position)

Step 1: Input list [12,23,3,-45].
Step 2: Key23 → pos2.
Step 3: Output present at2.
Simple Way: For unsorted.

Example 2: Binary Search (Program 6-2)

Simple Explanation: Halve sorted.

def binarySearch(list, key):
        first = 0
        last = len(list) - 1
        while(first <= last):
                mid = (first + last)//2
                if list[mid] == key:
                        return mid
                elif key > list[mid]:
                        first = mid + 1
                elif key < list[mid]:
                        last = mid - 1
        return -1
list1 = [] 
print ("Create list ascending")
num = int(input())
while num!=-999:
    list1.append(num)
    num = int(input())
n = int(input("Key: "))
pos = binarySearch(list1,n)
if(pos != -1):
    print( n,"at", pos+1)
else:
    print (n,"not found")

Step 1: Input [1,3,4,5] key4 → mid match pos3.
Step 2: Unsorted input [12,8,3] key4 → not found.
Step 3: Assumes sorted.
Simple Way: Sorted input.

Example 3: Hash Search (Program 6-3)

Simple Explanation: %10 lookup.

def hashFind(key,hashTable):
    if (hashTable[key % 10] == key): 
        return ((key % 10)+1)   
    else:
        return None 
hashTable=[None]*10
print("HashTable:",hashTable)
L = [34, 16, 2, 93, 80, 77, 51] 
print("List", L)
for i in range(0,len(L)): 
    hashTable[L[i]%10] = L[i]
print("Hash contents: ") 
for i in range(0,len(hashTable)): 
    print("index=", i," , value =", hashTable[i])
key = int(input("Search: ")) 
position = hashFind(key,hashTable)
if position is None:
    print("Not present")
else:
    print("Present at ",position)

Step 1: Build table [80,51,2,93,34,None,16,77,None,None].
Step 2: Key16 %10=6 match pos7.
Step 3: Output present at7.
Simple Way: Direct index.

Tip: Run trace tables; vary lists (e.g., collisions manual).

Subtopic	Key Points	Examples	Mnemonics/Tips
Linear	Seq: Start to end, O(n). Best1/Worst n: First/last. Unsored small.	Key17:4 comps.	SLB (Seq Linear Best). Tip: "Line Up Check All" – No skip.
Binary	Halve: Sorted O(log n). Mid: //2 compare. Iter log n max.	Key2:4 iters.	BHM (Binary Halve Mid). Tip: "Bi-Sect Midway" – Divide conquer.
Hashing	Direct: %size O(1). Collision: Same hash. Table list.	34%10=4.	HDC (Hash Direct Collision). Tip: "Hash Home Instant" – One step.
Complexity	L n, B log, H 1. Avg/worst.	1000:1000/10/1.	NLH (N Log One). Tip: "Need Less Halves" – Scale wise.
Apps	B: Dict, DB. H: Routing, compress.	Phone dir binary.	BDH (Binary Dict Hash). Tip: "Big Data Halve/Hash" – Real use.

Term/Process	Description	Example	Usage
Searching	Locate key	Find 17	Retrieval
Linear Search	Seq comp	Alg6.1	Unsored
Binary Search	Halve sorted	Alg6.2	Efficient
Hashing	Index func	%10	Direct
Key	Target item	17	Input
Hash Table	Hashed array	Table6.10	Storage
Hash Function	Map to index	Elem%size	Compute
Collision	Same index	16,26	Resolve
Perfect Hash	No collision	Unique map	Ideal
Sorted List	Ordered	[2,3,5]	Binary
Mid Position	(F+L)//2	Index5	Pivot
Sequential	Linear alias	Item by item	Simple
O(n)	Linear time	Worst linear	Scale
O(log n)	Log time	Binary	Efficient
O(1)	Constant	Hash	Fast
Iteration	Binary step	4 for15	Halve
Comparison	Key vs elem	4 for17	Work
Unsuccessful	Not found	n comps	Full scan
Successful	Found pos	Pos4	Early stop
Remainder Method	% size hash	34%10=4	Simple
Floor Division	// mid	10//2=5	Binary
Chaining	Collision list	Slot lists	Resolve adv
Probing	Next slot	Open addr	Resolve

Search Processes Step-by-Step

Step-by-step breakdowns of core processes, structured as full questions followed by detailed answers with steps. Visual descriptions; focus on actionable Q&A with examples from chapter.