NCERT Solutions Class 12, Computer Science, Chapter- 6, Searching
Exercise
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.
Solution:
Element 8 is found at position 4 after 4 comparisons.
Element 1 is found at position 1 after 1 comparisons.
Element 99 is not found in the list.
Element 44 is found at position 10.
2. Use the linear search program to search the key with value 8 in the list having duplicate values such as [42, -2, 32, 8, 17, 19, 42, 13, 8, 44]. What is the position returned? What does this mean?
Solution:
Position returned = 4
This means that linear search always returns the first position where the element is present if it is present multiple times in the list.
The linear search function is written as under:
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
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.
Solution:
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 in your list? "))
print("Enter each element and press enter: ")
for i in range(0,maximum):
n = int(input())
list1.append(n)
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)
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.
Solution:
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = [ 2, 3, 4, 10, 24, 34, 67, 99, 100, 133 ]
x = int(input("Enter the key to be searched: "))
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at position", str(result+1))
else:
print("Element is not present in array")
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 to find each of these numbers in the list.
-
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 list and note the number of key comparisons required to find these numbers in the list.
-
Use binary search to determine the position of 1, 5, 55 and 99 in the sorted list. Record the number of iterations required in each case.
Solution:
According to the Linear Search algorithm the position and number of comparisons for the elements are given as:
1: not found in the array and the number of comparisons is 24.
5: position = 13, number of comparisons is 13.
55: position = 23, number of comparisons are 23.
99: position = 21, number of comparisons are 21.
After sorting,
list = [5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]
1: not found in the array and the number of comparisons is 24.
5: position = 1, number of comparisons is 1.
55: position = 12, number of comparisons are 12.
99: position = 24, number of comparisons are 24.
By applying Binary Search:
1: not found in the array
5: position = 1
55: position = 12
99: position = 24
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 in the list. Also note the number of key comparisons required to find these words in the list.
-
Use a Python function to sort the list.
-
Again, use linear search to determine the position of Amazing, Perfect, Great and Wondrous in the list and note the number of key comparisons required to find these words in the list.
-
Use binary search to determine the position of Amazing, Perfect, Great and Wondrous in the sorted list. Record the number of iterations required in each case.
Solution:
Linear Search without sorting:
def linearsearch(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = ["Perfect", "Stupendous", "Wondrous", "Gorgeous", "Awesome", "Mirthful", "Fabulous", "Splendid", "Incredible", "Outstanding", "Propitious", "Remarkable", "Stellar","Unbelievable", "Super", "Amazing"]
x = input("Enter key to be searched: ")
print("element found at index "+str(linearsearch(arr,x)+1))
-
Amazing: Position = 16, number of comparisons = 16
-
Perfect: Position = 1, number of comparisons = 1
-
Great: Position = element not found.
-
Wondrous: Position = 3, number of comparisons = 3
Linear Search after sorting:
def linearsearch(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = sorted(["Perfect", "Stupendous", "Wondrous", "Gorgeous", "Awesome", "Mirthful", "Fabulous", "Splendid", "Incredible", "Outstanding", "Propitious", "Remarkable", "Stellar","Unbelievable", "Super", "Amazing"])
print("Sorted list: ",arr)
x = input("Enter key to be searched: ")
print("element found at position "+str(linearsearch(arr,x)+1))
-
Amazing: Position = 1, number of comparisons = 1
-
Perfect: Position = 8, number of comparisons = 8
-
Great: Position = element not found.
-
Wondrous: Position = 16, number of comparisons = 16
Binary Search
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = sorted(["Perfect", "Stupendous", "Wondrous", "Gorgeous", "Awesome", "Mirthful", "Fabulous", "Splendid", "Incredible", "Outstanding", "Propitious", "Remarkable", "Stellar","Unbelievable", "Super", "Amazing"])
print(arr)
x = input("Enter the key to be searched: ")
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at position", str(result+1))
else:
print("Element is not present in array")
