Page 111 - Computer science 868 Class 12
P. 111
3.5.3 Searching Algorithms
Problem 10: Write an algorithm to search any number from an array using the LINEAR SEARCH technique.
Note: Linear search program is already covered in the Array chapter of this book.
Step 1: Start. Target Unsorted List
15 13 48 7 4 15 25 11
Step 2: Initialise loop variable i to 0 and index
position pos to -1. 1st Comparision
Step 3: Repeat Step 4 to Step 6 while i < n. 15 13 48 7 4 15 25 11
15≠13
Step 4: If A[i] = searchvalue then go to Step 5, 2nd Comparision
else go to Step 6.
15 13 48 7 4 15 25 11
Step 5: Initialise pos to i, and go to Step 7. 15≠48
3rd Comparision
Step 6: Increment i by 1.
15 13 48 7 4 15 25 11
Step 7: If pos != -1 then go to Step 8, else go to 15≠7
Step 9. 4th Comparison
Step 8: Display searchvalue “found at index” pos, 15 13 48 7 4 15 25 11
go to Step 10. 15≠4
5th Comparison
Step 9: Display searchvalue “not found”.
15 13 48 7 4 15 25 11
Step 10: Stop. 15=15
Problem 11: Write an algorithm to search any number from an array using the BINARY SEARCH technique.
Note: Binary search program is already covered in the Array chapter of this book.
This algorithm is written assuming array a[] is sorted in ascending order:
Step 1: Start.
Step 2: Initialise begin to 0, end to array length-1 and pos = -1.
Step 3: Repeat Step 3 to Step 8 while begin <= end.
Step 4: Calculate mid = (begin + end)/2.
Step 5: If a[mid] = search_value then initialise Binary Search
pos = mid and go to Step 9. 0 1 2 3 4 5 6 7 8 9
Step 6: If a[mid] < search_value then initialise Search 23 2 5 8 12 16 23 38 56 72 91
begin=mid+1. L=0 1 2 3 M=4 5 6 7 8 H=9
23 > 16
Step 7: If a[mid] > search_value then initialise take 2 half 2 5 8 12 16 23 38 56 72 91
nd
end=mid-1. 0 1 2 3 4 L=5 6 M=7 8 H=9
23 > 56
Step 8: If pos = -1 then go to Step 10 else go take 1 half 2 5 8 12 16 23 38 56 72 91
st
to Step 11. L=5,
Found23, 0 1 2 3 4 M=5 H=6 7 8 9
Step 9: Display search_value found at index Returns 5 2 5 8 12 16 23 38 56 72 91
pos, go to Step 12.
109
Implementation of Algorithms to Solve Problems 109

