2nd pu notes

2nd PUC Computer Science Chapter 6 Searching Notes | Bubble Sort, Selection Sort, Insertion Sort

Venkatesh A August 30, 2026 27 min read

2nd PUC / Class XII • Computer Science

Complete Short Notes & Exam Preparation Guide

Linear Search • Binary Search • Search by Hashing • Algorithms • Python Programs • Questions & Answers

Based on the NCERT textbook PDF — Class XII Computer Science, Chapter 6.

verakworld.com

Chapter Overview

Searching means locating a particular element in a collection of elements. The search result determines whether the particular element is present in the collection or not. If it is present, its position in the collection can also be found.

This chapter discusses three searching techniques:

Linear Search
Binary Search
Search by Hashing

⭐ Exam Point: The three major searching techniques covered in this chapter are Linear Search, Binary Search and Search by Hashing.

verakworld.com

6.1 Introduction

Searching: Searching means locating a particular element in a collection of elements. The search result determines whether that element is present in the collection or not. If it is present, its position can also be found.

We store many things in our home and find them later whenever required. Sometimes we remember the exact location of an item. At other times, we do not remember the exact location and therefore need to search for it.

Similarly, a computer stores a large amount of data so that it can be retrieved later as and when demanded by a user or a program.

Searching is an important technique in computer science. To design algorithms, programmers need to understand different ways in which a collection of data can be searched for retrieval.

⭐ Exam Point: A search can determine both the presence of a particular element and, when present, its position in the collection.

verakworld.com

6.2 Linear Search

Definition: Linear search is the most fundamental and simplest search method. It is an exhaustive searching technique in which every element of a given list is compared with the item to be searched, usually called the key.

In linear search, each element in the list is compared one by one with the key. The process continues until an element matching the key is found.

If a matching element is found, the search is successful. If no element matches the key after the entire list has been traversed, the search is unsuccessful, meaning that the key is not present in the list.

The comparison is performed in the same order in which elements occur in the list, beginning with the first element and moving towards the last element. Therefore, linear search is also called sequential search or serial search.

Suitable collection: Linear search is useful for collections that are small in size and unordered.

Algorithm 6.1 — Linear Search

Given a list numList of n elements and key value K, the algorithm finds the position of key K in numList.

LinearSearch(numList, key, n)

Step 1: SET index = 0

Step 2: WHILE index < n, REPEAT Step 3

Step 3: IF numlist[index] = key THEN
            PRINT “Element found at position”, index+1
            STOP
        ELSE
            index = index+1

Step 4: PRINT “Search unsuccessful”

Example 6.1 — Searching for 17

Consider the list:

numList = [8, -4, 7, 17, 0, 2, 19]

Here, n = 7 and the key to be searched is 17.

Table 6.1 — Elements in numList along with their index value

Index in numList	0	1	2	3	4	5	6
Value	8	-4	7	17	0	2	19

verakworld.com

Table 6.2 — Linear search for key 17

index	index < n	numList[index] = key	index = index + 1
0	0 < 7? Yes	8 = 17? No	1
1	1 < 7? Yes	-4 = 17? No	2
2	2 < 7? Yes	7 = 17? No	3
3	3 < 7? Yes	17 = 17? Yes	—

verakworld.com

After four comparisons, the algorithm finds key 17 and displays “Element found at position 4”.

Effect of the Position of the Key

If the list is arranged as:

[17, 8, -4, 7, 0, 2, 19]

and the key is 17, only one comparison is needed because the key is the first element.

Table 6.3 — Another arrangement

Index in numList	0	1	2	3	4	5	6
Value	17	8	-4	7	0	2	19

verakworld.com

Table 6.4 — Linear search for key 17

index	index < n	numList[index] = key	index = index + 1
0	0 < 7? Yes	17 = 17? Yes	1

verakworld.com

Minimum work: If the key is the first element, linear search makes only 1 comparison.

If the list is:

[8, -4, 7, 0, 2, 19, 17]

and the key is 17, the algorithm compares every element until the end. Therefore, when the key is the last element, linear search makes n comparisons, where n is the number of elements.

Maximum work: When the key is the last element, linear search requires n comparisons.

Unsuccessful Linear Search

If the key is not present in the list, the algorithm compares every element until the end. Therefore, it again requires n comparisons.

Program 6-1 — Linear Search

def linearSearch(list, key): #function to perform the search
    for index in range(0,len(list)):
        if list[index] == key: #key is present
            return index+1 #position of key in list
    return None #key is not in list
#end of function

list1 = [] #Create an empty list
maximum = int(input("How many elements in your list? "))
print("Enter each element and press enter: ")
for i in range(0,maximum):
    n = int(input())
    list1.append(n) #append elements to the list
print("The List contents are:", list1)
key = int(input("Enter the number to be searched:"))
position = linearSearch(list1, key)
if position is None:
    print("Number",key,"is not present in the list")
else:
    print("Number",key,"is present at position",position)

Output

How many elements in your list? 4
Enter each element and press enter:
12
23
3
-45
The List contents are: [12, 23, 3, -45]
Enter the number to be searched:23
Number 23 is present at position 2

⭐ Program Point: The function returns the position of the key when it is present and returns None when the key is not in the list.

verakworld.com

6.3 Binary Search

Consider finding the meaning of the word Zoology in an English dictionary. Since the words are arranged alphabetically, it is more sensible to search in the second half. For the word Biology, searching in the first half is more sensible.

This is possible because words in an English dictionary are arranged in alphabetical order. If the words were not arranged alphabetically, a linear search would be needed.

Binary Search: Binary search is a search technique that makes use of the ordering of elements in a list to quickly search for a key.

For numeric values, the list may be arranged in ascending or descending order according to key values. For textual data, it may be arranged alphabetically from a to z or from z to a.

How Binary Search Works

In binary search, the key is compared with the element in the middle of a sorted list. There are three possibilities:

The middle element itself matches the key.
The middle element is greater than the key.
The middle element is smaller than the key.

Sorted List

↓

Find Middle Element

↓

Compare Middle Element with Key

↓

Match → Search Successful

Greater → Search First Half

Smaller → Search Second Half

verakworld.com

If the middle element matches the key, the search is successful and ends.

If the middle element is greater than the key, the key, if present, must be in the first half. Therefore, the second half can be ignored.

If the middle element is less than the key, the key, if present, must be in the second half. Therefore, the first half can be ignored.

This splitting and reduction continues until the key is found or the remaining list consists of only one item. If that item is not the key, the search is unsuccessful.

⭐ Essential condition: Binary search requires the list to be arranged in some order, that is, the list needs to be sorted.

Middle Position for an Even Number of Elements

If the list contains an even number of elements, the middle value is calculated using the floor division operator //.

For 10 elements: mid = 10 // 2 = 5

Since the first element has index value 0, the sixth element is considered the middle element. If required, the list is divided into two parts where the first half contains 5 elements and the second half contains 4 elements.

Why It Is Called Binary Search

Intermediate comparisons that do not find the key still provide information about where the key may be found. They indicate whether the key is before or after the current middle position.

Each unsuccessful comparison reduces the number of elements remaining to be searched by half. Hence the name binary search.

Iteration in Binary Search

The textbook uses the term iteration rather than comparison for binary search because after every unsuccessful comparison, the search area is changed by redefining the first, middle and last positions before the next comparison.

Algorithm 6.2 — Binary Search

BinarySearch(numList, key)

Step 1: SET first = 0, last = n-1

Step 2: Calculate mid = (first+last)//2

Step 3: WHILE first <= last REPEAT Step 4

Step 4: IF numList[mid] = key
            PRINT “Element found at position”, mid+1
            STOP
        ELSE
            IF numList[mid] > key, THEN
                last = mid-1
            ELSE
                first = mid + 1

Step 5: PRINT “Search unsuccessful”

Example 6.2 — Searching for 17

Consider the sorted list of 15 elements:

numList = [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43]

Table 6.5 — Sorted numList with index values

Index in numList	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Value	2	3	5	7	10	11	12	17	19	23	29	31	37	41	43

verakworld.com

Working

Stage	first	last	mid	numList[mid]	Result
At Start	0	14	(0+14)//2 = 7	17	17 = 17 → Yes
Iteration 1	0	14	7	17	Key found; search terminates

verakworld.com

The algorithm requires only 1 iteration to display “Element found at position 8” because the key being searched is the middle element.

Minimum work in binary search: Binary search requires only 1 iteration when the key is the middle value of the list.

Important: The binary search algorithm does not change the list. After every pass, the search area gets reduced by half. Only the index of the element to be compared with the key changes in each iteration.

Searching for Key 2

Using the same sorted list, search for key 2.

In the first iteration, the middle value is 17. Since 2 is smaller than 17, only the first half is searched in the next iteration.

The number of elements reduces from 15 to 7, then to 3, and finally to 1.

Table 6.7 — Searching key = 2

Iteration	last	mid	numList[mid]	Key comparison	Decision
1	14	7	17	17 = 2? No	2 < 17 → first half
2	6	3	7	7 = 2? No	2 < 7 → first half
3	2	1	3	3 = 2? No	2 < 3 → first half
4	0	0	2	2 = 2? Yes	Key found

verakworld.com

The binary search algorithm makes 4 iterations to narrow the list to a single element and determine that key 2 is the first element. This represents the maximum work required for this given list.

Program 6-2 — Binary Search

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 = [] #Create an empty list
print ("Create a list by entering elements in ascending order")
print ("press enter after each element, press -999 to stop")
num = int(input())
while num!=-999:
    list1.append(num)
    num = int(input())
n = int(input("Enter the key to be searched: "))
pos = binarySearch(list1,n)
if(pos != -1):
    print( n,"is found at position", pos+1)
else:
    print (n,"is not found in the list ")

Output — Successful Search

Create a list by entering elements in ascending order
press enter after each element, press -999 to stop
1
3
4
5
-999
Enter the number to be searched: 4
4 is found at position 3

Output — Unsuccessful Search

Create a list by entering elements in ascending order
press enter after each element, press -999 to stop
12
8
3
-999
Enter the number to be searched: 4
4 is not found in the list

⭐ Program Point: The binary search program returns the index of the found key and displays the position using pos + 1. If the key is not found, the function returns -1.

verakworld.com

6.3.1 Applications of Binary Search

Searching a dictionary or a telephone directory.
Finding the element with minimum value in a sorted list.
Finding the element with maximum value in a sorted list.
Modified binary search techniques have applications in indexing databases.
Modified binary search techniques are used in implementing routing tables in routers.
They also have applications in data compression code.

verakworld.com

6.4 Search by Hashing

Hashing: Hashing is a technique that can be used to know the presence of a key in a list in just one step, when the key is present at the designated position determined by a hash function.

If the value at every index position in a list is already known, only a single comparison is required to check the presence or absence of a key.

Hashing makes searching operations very efficient. A formula called a hash function is used to calculate the value at an index in the list.

A hash function takes elements of a list one by one and generates an index value for every element. This generates a new list called the hash table.

Each index of the hash table can hold only one item and the positions are indexed by integer values starting from 0. The size of the hash table can be larger than the size of the list.

Remainder Method

A simple hash function that works with numeric values is the remainder method.

It takes an element from a list and divides it by the size of the hash table. The remainder generated is called the hash value.

h(element) = element % size(hash table)

Example — Hash Table with 10 Positions

An empty hash table having 10 positions can be represented as follows.

Table 6.8 — An Empty Hash Table with 10 Positions

Index / Position	0	1	2	3	4	5	6	7	8	9
Value	None	None	None	None	None	None	None	None	None	None

verakworld.com

Consider the list:

(34, 16, 2, 93, 80, 77, 51)

Applying the remainder method with a hash table size of 10 gives the following hash values.

Table 6.9 — Hash Function: element % 10

Element	34	16	2	93	80	77	51
Hash Value	34%10=4	16%10=6	2%10=2	93%10=3	80%10=0	77%10=7	51%10=1

verakworld.com

Table 6.10 — Generated Hash Table

Index	0	1	2	3	4	5	6	7	8	9
Value	80	51	2	93	34	None	16	77	None	None

verakworld.com

Searching Using a Hash Table

To search for a key, its index is calculated using the hashing function. The element at that index is then compared with the key.

This search operation involves just one comparison and hence the same amount of time is always required to search for a key irrespective of the size of the list, provided the key is stored at its designated position.

⭐ Exam Point: Hash-based searching requires only one key comparison when every element is present at its designated position determined by the hash function.

Program 6-3 — Use of Hashing to Find a Key

#Function to check if a key is present or not
def hashFind(key,hashTable):
    if (hashTable[key % 10] == key): #key is present
        return ((key % 10)+1) #return the position
    else:
        return None #key is not present
#end of function

#create hashTable with 10 empty positions
hashTable=[None, None, None, None, None, None, None, None, None, None]

print("We have created a hashTable of 10 positions:")
print(hashTable)
L = [34, 16, 2, 93, 80, 77, 51]
print("The given list is", L[::] )
# Apply hash function
for i in range(0,len(L)):
    hashTable[L[i]%10] = L[i]

print("The hash table contents are:" )
for i in range(0,len(hashTable)):
    print("hashindex=", i," , value =", hashTable[i])
key = int(input("Enter the number to be searched:"))
position = hashFind(key,hashTable)
if position is None:
    print("Number",key,"is not present in the hash table")
else:
    print("Number ",key," present at ",position, " position")

Output

We have created a hashTable of 10 positions:
[None, None, None, None, None, None, None, None, None, None]
The given list is [34, 16, 2, 93, 80, 77, 51]
The hash table contents are:
hashindex= 0 , value = 80
hashindex= 1 , value = 51
hashindex= 2 , value = 2
hashindex= 3 , value = 93
hashindex= 4 , value = 34
hashindex= 5 , value = None
hashindex= 6 , value = 16
hashindex= 7 , value = 77
hashindex= 8 , value = None
hashindex= 9 , value = None
Enter the number to be searched:16
Number 16 present at 7 position

verakworld.com

6.4.1 Collision

Collision: Collision occurs in hashing when two or more elements map to the same position in the hash table.

The hashing technique works properly if every element of the list maps to a unique location in the hash table.

Consider:

[34, 16, 2, 26, 80]

With the hash function list[i] % 10, both 16 and 26 produce the hash value 6.

Element	Hash Function	Hash Value
16	16 % 10	6
26	26 % 10	6

verakworld.com

Since two elements cannot occupy the same position according to the hash table definition, this is a problematic situation called collision in hashing.

Collision Resolution: The mechanism for placing other items having the same hash value in the hash table is called collision resolution.

Collision can be resolved in many ways, but the methods of collision resolution are beyond the scope of the textbook chapter.

Perfect Hash Function

Perfect Hash Function: If every item of the list maps to a unique index in the hash table, the hash function is called a perfect hash function.

If a hash function is perfect, collision will never occur.

Other Hash Function Techniques Mentioned

Apart from modulo division, the chapter mentions the following hash-function techniques:

Integer division
Shift folding
Boundary folding
Mid-square function
Extraction
Radix transformation

The chapter states that these methods are beyond its scope for discussion.

Time Required for Hash Functions

The time taken by different hash functions may be different, but it remains constant for a particular hash function.

The advantage of hashing is that the time required to compute the index value is independent of the number of items in the search list.

The cost of computing the hash function must be small enough to make hashing-based searching more efficient than other search methods.

⭐ Remember: A perfect hash function maps every input key to a unique index, so collisions do not occur.

verakworld.com

Chapter Summary

Searching

Searching means trying to locate a particular element called a key in a collection. It tells whether the key is present and, if present, its position.

Linear Search

Checks elements one at a time without skipping any element. It is useful for a small unsorted list. The time taken increases as the list size increases.

Binary Search

Works on a sorted or ordered list. It compares the middle element with the key and continues in the appropriate half.

Hashing

Uses a hash function to calculate the position of a key. Hash-based searching can use one key comparison when the element is at its designated position.

Collision

When two elements map to the same slot in a hash table, it is called collision.

Collision Resolution

The process of identifying a slot for the second and further items in a hash table when collision occurs.

Perfect Hash Function

Maps every input key to a unique index in the hash table. Therefore, collisions never occur.

Binary Search Key Idea: Each unsuccessful comparison gives information about whether the key is before or after the current middle position, allowing the search area to be reduced.

Hashing Key Idea: The hash function calculates the position of a key using the key itself and the chosen hashing formula.

verakworld.com

Questions & Answers

1-Mark Questions

1 Mark

1. What is searching?

Searching means locating a particular element in a collection of elements.

1 Mark

2. What is a key in searching?

The particular item to be searched in a collection is usually referred to as the key.

1 Mark

3. Name the simplest search method discussed in the chapter.

Linear search.

1 Mark

4. What are the other names for linear search?

Sequential search and serial search.

1 Mark

5. What condition is required for binary search?

The list needs to be sorted or arranged in some order.

1 Mark

6. What operator is used for floor division in Python?

The // operator.

1 Mark

7. What is hashing?

Hashing is a technique used to know the presence of a key in a list in just one step when the key is stored at its designated position.

1 Mark

8. What is a hash table?

A hash table is a new list generated by a hash function, where elements are placed at calculated index positions.

1 Mark

9. Write the remainder-method hash function given in the chapter.

h(element) = element % size(hash table)

1 Mark

10. What is collision in hashing?

Collision occurs when two or more elements map to the same position in the hash table.

1 Mark

11. What is a perfect hash function?

A hash function that maps every item to a unique index in the hash table is called a perfect hash function.

2-Mark Questions

2 Marks

1. Explain linear search.

Linear search compares every element of a list with the key one by one in the order in which the elements occur. The search is successful when a matching element is found; otherwise, after traversing the complete list, the search is unsuccessful.

2 Marks

2. Why is linear search also called sequential or serial search?

Because the elements are compared one by one in sequence, beginning with the first element and moving towards the last element.

2 Marks

3. When does linear search require n comparisons?

Linear search requires n comparisons when the key is the last element of the list or when the key is not present in the list.

2 Marks

4. Why must a list be sorted for binary search?

Binary search uses the ordering of elements to decide which half of the list may contain the key. Without an ordered list, this decision cannot be made.

2 Marks

5. Explain the three possible results of comparing the key with the middle element in binary search.

The middle element may be equal to the key, greater than the key, or smaller than the key. If equal, the search ends successfully. If greater, the first half is searched. If smaller, the second half is searched.

2 Marks

6. What is collision resolution?

It is the process of identifying a slot for the second and further items in a hash table when collision occurs.

3-Mark Questions

3 Marks

1. Explain how binary search reduces the search area.

Binary search compares the key with the middle element of a sorted list. If the middle element is greater than the key, the second half is ignored and only the first half is searched. If the middle element is smaller than the key, the first half is ignored and only the second half is searched. This process continues, reducing the search area by half after an unsuccessful comparison.

3 Marks

2. Explain the remainder method of hashing.

The remainder method works with numeric values. An element is divided by the size of the hash table and the remainder is obtained as the hash value. The formula given in the chapter is: h(element) = element % size(hash table).

3 Marks

3. Explain collision with an example from the chapter.

For the list [34, 16, 2, 26, 80] and the hash function list[i] % 10, both 16 and 26 produce hash value 6. Therefore, both elements map to the same position. This situation is called collision.

4/5-Mark Questions

4/5 Marks

1. Explain linear search with its algorithm and Python program.

Write the definition and working of linear search, explain that the elements are checked sequentially, reproduce Algorithm 6.1 and write Program 6-1 as given in the textbook.

4/5 Marks

2. Explain binary search with its algorithm and Python program.

Explain that binary search works on a sorted list, compare the key with the middle element, choose the appropriate half, reproduce Algorithm 6.2 and write Program 6-2 as given in the textbook.

4/5 Marks

3. Explain hashing, hash function, hash table and collision.

Explain hashing, the remainder-method formula, creation of the hash table, searching using the calculated index, and collision when multiple elements map to the same position.

verakworld.com

📝 Important Questions

1 Mark

Define searching.
What is a key?
What is linear search?
Name the two other terms used for linear search.
When is linear search useful?
What is binary search?
What is the essential condition for binary search?
What does the // operator do?
Define hashing.
Define hash function.
Define hash table.
What is collision?
What is collision resolution?
What is a perfect hash function?

2 Marks

Explain the working of linear search.
Explain successful and unsuccessful linear search.
When does linear search perform the minimum amount of work?
When does linear search perform the maximum amount of work?
Explain the three possible outcomes of a binary-search middle-element comparison.
Why does binary search require a sorted list?
Explain the remainder method.
Explain collision in hashing.

3 Marks

Explain binary search with an example.
Explain why the search area is reduced by half in binary search.
Explain the creation of a hash table using the remainder method.
Explain collision and collision resolution.
Explain the concept of a perfect hash function.

4/5 Marks

Write and explain Algorithm 6.1 for linear search.
Write Program 6-1 for linear search and explain its output.
Write and explain Algorithm 6.2 for binary search.
Write Program 6-2 for binary search and explain its output.
Explain the working of binary search using the example of key 2.
Explain search by hashing with the remainder method.
Write Program 6-3 and explain how hashing is used to find a key.
Explain collision and perfect hash function.

Board-Exam Preparation: Give special attention to the definitions, algorithms, Python programs, hash-function formula, examples, tables, collision and perfect hash function. These are central concepts presented in this chapter.

verakworld.com

⚡ Quick Revision

Important Definitions

Searching
Linear Search
Binary Search
Hashing
Collision
Collision Resolution
Perfect Hash Function

Important Terms

Key
Search result
Sorted list
Hash function
Hash value
Hash table
Iteration

Important Formulas

h(element) = element % size(hash table)

mid = (first + last) // 2

Important Algorithms

Algorithm 6.1 — Linear Search
Algorithm 6.2 — Binary Search

Important Programs

Program 6-1 — Linear Search
Program 6-2 — Binary Search
Program 6-3 — Use of Hashing to Find a Key

Important Tables

Table 6.1 — Linear-search list
Table 6.2 — Linear-search working
Table 6.3 — Another list arrangement
Table 6.4 — Linear-search working
Table 6.5 — Sorted list
Table 6.7 — Binary search for key 2
Table 6.8 — Empty hash table
Table 6.9 — Hash values
Table 6.10 — Generated hash table

Linear Search — One-Minute Revision

Simple and fundamental search method.
Checks elements one by one.
Also called sequential or serial search.
Useful for small, unordered collections.
First element as key → 1 comparison.
Last element as key → n comparisons.
Key absent → n comparisons.

Binary Search — One-Minute Revision

Uses ordering of elements.
List must be sorted.
Compares key with middle element.
Equal → search successful.
Middle element greater → search first half.
Middle element smaller → search second half.
Search area is reduced by half.
Uses the term iteration because the search area and first, middle and last positions change.

Hashing — One-Minute Revision

Uses a hash function to calculate an index.
Creates a hash table.
Remainder method is given for numeric values.
Hash value is the remainder obtained by division.
Search can involve one comparison when the key is at its designated location.
Two elements mapping to one slot causes collision.
Collision resolution identifies slots for additional items.
Perfect hash function gives every item a unique index.

Important Difference — Linear Search vs Binary Search

Basis	Linear Search	Binary Search
Searching method	Checks elements one by one.	Checks the middle element and reduces the search area.
List arrangement	Useful for an unordered list.	Requires a sorted/ordered list.
Search area	Elements are checked sequentially.	Search area is reduced by half after an unsuccessful comparison.
Important term	Comparison	Iteration

verakworld.com

Important Difference — Collision vs Perfect Hash Function

Basis	Collision	Perfect Hash Function
Meaning	Two or more elements map to the same hash-table position.	Every item maps to a unique index.
Result	Multiple elements require a mechanism for placement.	Collision never occurs.

verakworld.com

Important Diagrams / Structures to Revise

Linear-search sequential comparison process.
Binary-search middle-element decision process.
Reduction of the binary-search area by half.
Hash-table index structure.
Hash-value-to-index mapping.
Collision where two elements map to the same slot.

Element / Key

↓

Hash Function

↓

Calculated Hash Value / Index

↓

Hash Table Position

verakworld.com

Textbook Exercise — Chapter 6

1.

Using linear search determine the position of 8, 1, 99 and 44 in the list:

[1, -2, 32, 8, 17, 19, 42, 13, 0, 44]

Draw a detailed table showing the values of the variables and the decisions taken in each pass of linear search.

2.

Use the linear search program to search the key with value 8 in the list having duplicate values:

[42, -2, 32, 8, 17, 19, 42, 13, 8, 44]

What is the position returned? What does this mean?

3.

Write a program that takes as input a list having a mix of 10 negative and positive numbers and a key value. Apply linear search to find whether the key is present in the list or not. If the key is present it should display the position of the key in the list; otherwise it should print an appropriate message. Run the program for at least 3 different keys and note the result.

4.

Write a program that takes as input a list of 10 integers and a key value and applies binary search to find whether the key is present in the list or not. If the key is present it should display the position of the key in the list; otherwise it should print an appropriate message. Run the program for at least 3 different key values and note the results.

5.

Following is a list of unsorted/unordered numbers:

[50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]

Use linear search to determine the position of 1, 5, 55 and 99 in the list. Also note the number of key comparisons required.
Use a Python function to sort/arrange the list in ascending order.
Again use linear search to determine the position of 1, 5, 55 and 99 in the sorted list and note the number of key comparisons.
Use binary search to determine the position of 1, 5, 55 and 99 in the sorted list. Record the number of iterations required.

6.

Write a program that takes as input the following unsorted list of English words:

[Perfect, Stupendous, Wondrous, Gorgeous, Awesome, Mirthful, Fabulous, Splendid, Incredible, Outstanding, Propitious, Remarkable, Stellar, Unbelievable, Super, Amazing]

Use linear search to find the position of Amazing, Perfect, Great and Wondrous. Note the number of key comparisons.
Use a Python function to sort the list.
Again use linear search to determine the positions and comparisons.
Use binary search to determine the positions and record the number of iterations.

7.

Estimate the number of key comparisons required in binary search and linear search if we need to find the details of a person in a sorted database having 2³⁰ (1,073,741,824) records when the details of the person being searched lies at the middle position in the database. What do you interpret from your findings?

8.

Use the hash function:

h(element) = element % 11

to store the collection of numbers:

[44, 121, 55, 33, 110, 77, 22, 66]

Display the hash table created. Search if the values 11, 44, 88 and 121 are present in the hash table, and display the search results.

9.

Write a Python program by considering a mapping of list of countries and their capital cities such as:

CountryCapital = {
    'India':'New Delhi',
    'UK':'London',
    'France':'Paris',
    'Switzerland':'Berne',
    'Australia':'Canberra'
}

Let us presume that the hash function is the length of the Country Name. Take two lists of appropriate size: one for keys (Country) and one for values (Capital). To put an element in the hash table, compute its hash code by counting the number of characters in Country, then put the key and value in both lists at the corresponding indices.

For example, India has a hash code of 5. So, India is stored at the 5th position (index 4) in the keys list and New Delhi at the 5th position (index 4) in the values list.

Hash Table Structure Given in the Exercise

Hash index = length of key – 1	List of Keys	List of Values
0	None	None
1	UK	London
2	None	None
3	Cuba	Havana
4	India	New Delhi
5	France	Paris
6	None	None
7	None	None
8	Australia	Canberra
9	None	None
10	Switzerland	Berne

verakworld.com

Now search the capital of India, France and the USA in the hash table and display the result.

verakworld.com

Final Revision Section

Before the Examination, Remember These Points

Searching locates a key in a collection.
Linear search checks elements one by one.
Linear search is also called sequential or serial search.
Linear search is useful for small unordered lists.
Linear search needs n comparisons when the key is last or absent.
Binary search uses an ordered/sorted list.
Binary search compares the key with the middle element.
A greater middle value sends the search towards the first half.
A smaller middle value sends the search towards the second half.
Binary search reduces the search area by half.
For an even number of elements, the chapter uses floor division // for the middle calculation.
Hashing calculates an index using a hash function.
The remainder method is h(element) = element % size(hash table).
Hash table positions are indexed by integer values starting from 0.
Collision occurs when two or more elements map to the same slot.
Collision resolution deals with placement of further items after collision.
A perfect hash function maps every item to a unique index.

Core Formulas

mid = (first + last) // 2

h(element) = element % size(hash table)

verakworld.com

Core Programs to Practise

Program 6-1 — Linear Search
Program 6-2 — Binary Search
Program 6-3 — Use of Hashing to Find a Key

verakworld.com

Core Concepts to Revise

Linear Search

Sequential comparison of list elements with the key.

Binary Search

Middle-element comparison on a sorted list.

Hashing

Calculation of a key’s designated index using a hash function.

Collision

More than one element maps to the same hash-table position.

verakworld.com

Final Exam Tip: Practise the algorithms and Python programs exactly according to the chapter, understand the working tables for linear and binary search, and remember the hashing formula and collision definitions.