In: Computer Science
Typed please.How can we implement efficient search operations? In this area, we will discuss various algorithms, including sequential search, sorted search, and binary search. The characteristics of these algorithms will be analyzed, such as the running times and the type of lists they can be used with.
If we write a computer program to perform some task we need implement a suitable algorithm. There are so many algorithms are there to perform same task but we have to choose the best algorithm that should work very efficiently. We can calculate if a program is efficient or not by using time complexity and space complexity. These two are basic measure to know which one is an efficient algorithm. suppose if an algorithm has best time complexity when compared to some other algorithms then we can say that particular algorithm is efficient for search operations.
1. sequential search: it is also called linear search. in this we have to take an element to search. compare that element with each number in sequential manner. like wise we have to compare element with all other elements. if a number is found exit from the program otherwise continue the process till the end of list and exit.
example: we have list of numbers
20 95 87 12 78 65 25 3
now search for a number 87
compare 87 with 20 that is if(87==20) match is not found, now courser will move to next number
compare 87 with 95 again match is not found , now move to next number
compare 87 with 87 yes match is found, finally output will be printed. like this we have compare.
2. sorted search: In sorted search we have to take array with sorted manner. either from ascending order or descending order. now take one number and compare with each element. if the element is found at a location then the output will be the index of particular element otherwise it exits from the program.
for example lets take an array with sorted elements
array{ -4, -3,0,4,11,65,76,87}
search for an element 11
compare 11 with -4 match not found
compare 11 with -3 match not found
compare 11 with 0 match not found
compare 11 with 4 match not found
compare 11 with 11 match found,. so the output will be the index of that number
output is: 4 [ 11 is placed at 4 th location]
if suppose compare 5
compare 5 with each element 5 is not matched with any element so it will exit from the program.
3. binary search: Binary search is simple complex than remaining algorithms but very quickly it gives the efficient search operation. first it takes a list of sorted array. take a mid point by counting the num of elements. first element is lowest point and last element highest point ,middle element is mid point.
example: if we have 8 elements {5,18,26,54,96,102,156,170} take mid point that is 8/2=4
so 4 is the mid point
L=0 mid=4 H=7
5 18 26 54 96 102 156 170
so the mid point value is 54
our search element is 18, compare 18 with mid value 54 (54>18) 18 is a smaller than 54 so 18 is placed in left side of the mid point.
now compare 18 with left sub tree of element 5 match not found
now compare 18 with 18 yes match found so that out will the position of the element that is 2nd position
Among all these algorithms binary search operation is very efficient because searching time reduced when compare to other algorithms. Based on the condition we can easily identify the element is placed in left or right of the sub tree. the time complexity of binary search is O(logn)
In sequential search we have to search till the end of the list. it take longer process when we have large list.
In sorted search also we have to search till the end of the list. it is also not suitable for longer list of arrays.
binary search is an efficient search algorithm, it reduces the searching time.