International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395-0056
Volume: 07 Issue: 01 | Jan 2020
p-ISSN: 2395-0072
www.irjet.net
A Survey on Different Searching Algorithms Ahmad Shoaib Zia1 1M.Tech scholar at the Department of Computer Science, Sharda University Greater Noida, India
---------------------------------------------------------------------***---------------------------------------------------------------------
Abstract - This paper presents the review of certain
important and well discussed traditional search algorithms with respect to their time complexity, space Complexity , with the help of their realize applications. This paper also highlights their working principles. There are different types of algorithms and techniques for performing different tasks and as well as same tasks, with each having its own advantages and disadvantages depending on the type of data structure. An analysis is being carried out on different searching techniques on parameters like space and time complexity. Dependent upon the analysis, a comparative study is being made so that the user can choose the type of technique used based on the requirement. Key Words: Searching algorithms, binary search, linear search, hybrid search, interpolation search, and jump search.
b) Internal searching: [3] Internal searching is that type of searching technique in which there is fewer amounts of data which entirely resides within the computer’s main memory. In this technique data resides within the main memory on.
2. Exiting Search Algorithms 2.1 Binary Search It is a fast search algorithm [9] as the run-time complexity is Ο (log n). Using Divide and conquer Principle for it search algorithm. This algorithm performs better for sorted data collection. In binary search, we first compare the key with the item in the middle position of the data collection. If there is a match, we can return immediately. If the key is less than middle key, then the item must lie in the lower half of the data collection; if it is greater, then the item must lie in the upper half of the data collection [8]. Algorithm
1. INTRODUCTION A searching algorithm [1] [2] [3] is that type of algorithm that allows the efficient retrieval of a particular item from a set of many items. Searching is the algorithm process of finding a specific item in a collection of item. A search typically answers the user whether the item he searched for is present or not. Computer systems are often used to store large amounts of data from which individual records can be retrieved according to some search criterion so, it is our need to search and fetch the data in that manner so that it will take lesser time and will be efficient. [2] For this purpose some approaches are needed that not only saves our time but also fetches the required data efficiently. In this study we will discuss linear search, binary search, Interpolation search, hybrid search, algorithms on the basis of their efficiency and time complexity.
1. 2. 3. 4. 5. 6.
7.
Input an array A of n elements I sorted form. LB=0,UB=n; mid=int((LB+UB))/2) Repeat step 4 and 5 while(LB<=UB and (A[mid]!=item) If (item<A[mid]) UB=mid-1 Else LB=mid+1 mid=int((LB+UB)/2) If (A[mid]==item) Print” Item is found” Else Print ”Item is not found” End.
Searching falls into two categories: a) External searching: External searching [3] means searching the records using keys where there are many records, which resides in the files stored on disks. This is the type of searching in which the data on which searching is done resides in the secondary memory storage like hard disk or any other external storage peripheral device.
© 2020, IRJET
|
Impact Factor value: 7.34
|
ISO 9001:2008 Certified Journal
|
Page 1580
International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395-0056
Volume: 07 Issue: 01 | Jan 2020
p-ISSN: 2395-0072
www.irjet.net
Illustration 3
An array with seven elements, search for “5”: 12
4
95
32
7
24
5
12
4
95
32
7
24
5
12
4
95
32
7
24
5
12
4
95
32
7
24
5
12
4
95
32
7
24
5
12
4
95
32
7
24
5
12
4
95
32
7
24
55 found Return 5
5
Algorithm Here A is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in A [3].
4. 5.
6.
Set ctr=L Repeat steps 3 through 4 until ctr>Upper bound. If A[ctr]==ITEM then { print “Search successful” Print ctr, ”is the location of”, ITEM Go out of loop } 4.ctr=ctr+1 If ctr>Upper bound then Print ”Search unsuccessful” End.
Impact Factor value: 7.34
55
H
M
12
12
24
24
29
29
73
41
55
73
L
M
H
41
55
73
Hybrid Search algorithm [6] combines properties of both linear search and binary search and provides a better and efficient algorithm. This algorithm can be used to search in an unsorted array while taking less time as compared to the linear search algorithm. As mentioned this algorithm is combines two searching algorithms, viz. Linear Search and Binary Search. As with Hybrid Search algorithm, the array is divided into two sections and then searched in each of the sections. The algorithm starts with comparing the key element to be searched with the two extreme elements of the array, the first and the last, as well as the middle element. If a match is found, the index value is returned. However, if it is not, the array is divided into two sections, from the middle index. Now the search is carried out in the section on the left in a similar way. The extreme elements and the middle element of the left division are compared with the key value for a match, which if found, returns the index value. If not, the left section is again divided into two parts and this process goes on till a match is found in the left section [5]. If no match is found in the left division, then the algorithm moves on to the right division, and the same procedure is carried out to find a match for the key value. Now, if no value is found that matches the key value even after searching through all sections, then it is further divided and the process repeats iteratively until it reaches the atomic state. If the value is not present in the array, as a result of which the algorithm returns -1.
1. mid = ( low + high )/2 2. if a[low] = key then return low 3. else if a[high] = key then return high 4. else if a[mid] = key then return mid 5. else if low >= high – 2 then return -1 6. else 7. p = recLinearBinary(a, low + 1, mid – 1, key) 8. if p = -1 9. p = recLinearBinary(mid + 1, high – 1, key) 10. return p
Searching for 55 in 7-element array:
|
3
41
Algorithm
Illustration
© 2020, IRJET
3
29
2.3 Hybrid Search
2.2 Linear Search
3.
24
L 55>29, take the 2nd half
Linear search is a simple search algorithm [8]. It is a sequential search which performed on sequences of numbers that are ascending or descending or unordered. And it checks each and every element of the entire list to search a particular data from the list. If the comparison is equal, then the search is stopped and declared successful. For a list with n items, the best case is when the value of item to be searched is equal to the first element of the list, in this case only one comparison is needed. Worst case is when the value is not in the list or occurs only once at the end of the list, in this case n comparisons are needed [9].
1. 2.
12
|
ISO 9001:2008 Certified Journal
|
Page 1581
International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395-0056
Volume: 07 Issue: 01 | Jan 2020
p-ISSN: 2395-0072
www.irjet.net
Illustration
Illustration
Searching for 4 in 9-elments array: Searching for 2 in 8-elemetnts array: End
Start 14
5
14
5
71
37
71
37
56
56
2
2
98
98
11
1
2
4
7
9
12
13
14
17
Array [0]
Array [1]
Array [2]
Array [3]
Array [4]
Array [5]
Array [6]
Array [7]
Array [8]
1
2
4
7
9
12
13
14
17
11
14
5
71
37
56
2
98
11
Array [0]
Array [1]
Array [2]
Array [3]
Array [4]
Array [5]
Array [6]
Array [7]
Array [8]
14
5
71
37
56
2
98
11
1
2
4
7
9
12
13
14
17
Array [0]
Array [1]
Array [2]
Array [3]
Array [4]
Array [5]
Array [6]
Array [7]
Array [8]
2.4 Interpolation Search Interpolation search algorithm [7] is improvement over Binary search. The binary search checks the element at middle index. But interpolation search may search at different locations based on value of the search key. The elements must be in sorted order in order to implement interpolation search. As mentioned the Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. [3] Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side. Algorithm 1. 2.
3. 4. 5. 6.
Initialize the values of start to 0 and end to n-1. Calculate the value of
2.5 Jump Search Jump search algorithm, [4] also called as block search algorithm. Only sorted list of array or table can use the Jump search algorithm. In jump search algorithm, it is not at all necessary to scan every element in the list as we do in linear search algorithm. We just check the m element and if it is less than the key element, then we move to the m + m element, where all the elements between m element and m + m element are skipped. [7] This process is continued until m element becomes equal to or greater than key element called boundary value. The value of m is given by m = √n, where n is the total number of elements in an array. Once the m elements attain the boundary value, a linear search is done to find the key value and its position in the array. And the numbers of comparisons are equal to (n/m + m -1). [3] It must be noted that in Jump search algorithm, a linear search is done in reverse manner that is from boundary value to previous value of m. Algorithm
where K is an array and p is the search key. If K[x]==p, then stop and return. If K[x]!=p, then If p>K[x] then make start=x+1 If p<K[x] then make end=x-1. Repeat step 2 till the search element is found. End
1. 2.
3. 4.
© 2020, IRJET
|
Impact Factor value: 7.34
|
Set i=0 and m= √n Compare A[i] with item. If A[i] != item and A[i] < item, then jump to the next block. Also, do the following: 1. Set i = m 2. Increment m by √n Repeat the step 2 till m < n-1 If A[i] > item, then move to the beginning of the current block and perform a linear search. 1. Set x = i
ISO 9001:2008 Certified Journal
|
Page 1582
International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395-0056
Volume: 07 Issue: 01 | Jan 2020
p-ISSN: 2395-0072
2.
Compare A[x] with item. If A[x]== item, then print x as the valid location else set x++ Repeat Step 4.1 and 4.2 till x < m
3. 5.
www.irjet.net
End
Illustration
Best case
Best case
Best case
=O(1)
=O(1)
=O(1)
Average
Average
Average
Time
Case
case
case
Average
Complexit
=O(log n)
=O(n)
=O(log2n)
case
=O(1)
y Analysis
Searching for 24 in 9-elments array: n=9 m = √9 = 3
7 < 24
30 > 24 Do linear search backward
2
5
7
11
24
30
45
78
=O(log(log
Worst Worst
Case
Worst
case
=O(n)
Case
=O(log n)
99
=O(n)
N)) Worst case =O(n)
2
5
2
5
2
5
7
11
7
7
11
11
24
30
24
24
45
30
45
30
45
78
99
78
99
78
99
Advantage
3. Comparison table of search algorithms
Average
Simple to
Takes
Execution
It is very
case and
understa
lesser
time for
useful
worst
nd,
time
average
when
case
Works on
compare
case is
jumping
order
both
d to
much
back is
are
sorted
linear
lower
significant
better
and
search
than
ly lower
than that
unsorted
and array
linear and
than
of linear
elements.
need not
binary
jumping
search.
Easy to
be
search.
forward.
Worst
implemen
sorted.
case
t.
More efficient
order is
than
also
linear
better
search.
Algorithm
Binary
Linear
Hybrid
Interpolat
Jump
s
Search
Search
Search
ion Search
Search
As well-
Sequentia
Combine
Improved
Also
interpola
known
lly Checks
s the
variant of
known as
tion
as half
the target
advantag
binary
block
search.
interval
element
es of
search.
search,
search or
in the list
Binary
Works on
where
logarith
until and
and
the
step
mic
unless it
Linear
probing
number is
search
is found
algorith
position of
calculated
which
or all the
ms and
required
from the
follows
element
provides
value to
list length
divides
are
an
search a
and
and
checked
effective
particular
searching
reduces
way to
data from
is done in
method.
search
a list.
some
for a
Works
interval of
given key
only on
blocks.
element
sorted
in an
elements.
Features
Best case
than
unsorted array, in
Works
Is not
The
Works
Works
only on
very
worst
only on
only on
sorted
efficient
case is n
sorted
sorted
elements
than
iteration.
elements
elements.
.
binary
and worst
Implemen
and
case is n
tation of
interpolat
iterations
this
Disadvant
ion
approach
age
search as
is
it
considere
requires
d to be
lot of
more
comparis
difficult
ons to
than
find a
binary
particular
search.
data.
limited time.
© 2020, IRJET
|
Impact Factor value: 7.34
|
ISO 9001:2008 Certified Journal
|
Page 1583
International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395-0056
Volume: 07 Issue: 01 | Jan 2020
p-ISSN: 2395-0072
www.irjet.net
4. Motivation During the research I carried out upon various searching algorithms and throughout reading various papers from different publishers. I was motivated to perform more and more research in this field which caused me to come up and publish a survey paper to find difference between different types of search algorithms and there best way to be suitable for data set. 5. Conclusion The paper discusses about various searching techniques. It shows the methodology for various searching techniques. Searching is one of the important operation of data structure. Different searching algorithms enable us to look for a particular data from the entire list. The analysis shows the advantages and disadvantages of various searching algorithms along with examples. We analyzed based on time complexity and space complexity. On analysis, we found that binary search is suitable for mid-sized data items and is applicable in arrays and in linked list, whereas jump search is best for large data items. Also we found that Hybrid search used for unsorted list with more elements. ACKNOWLEDGEMENT
First of all, I would like to thank the most merciful and the most gracious Allah who teaches and shows us the way of happiness of this and next word by the agency of his messenger the owner of honor Mohammad (peace be open him) and give command for learning the knowledge. I, Ahmad Shoaib Zia, would like to express my sincere appreciation to all those who provided me the possibility to complete this paper. I give a gratitude to my guide Prof. (Dr.) Nitin Rakesh and a special thanks from Dr. Mandeep Kaur whose contribution in stimulating suggestions and encouragement helped me to write this paper at the end a special thanks from my classmate Zubair Salarzai, he help me to write this paper.
[4] Jump Searching: A Fast Sequential Search Technique, S.L. Graham, R.L. Rivest, Ben Shneiderman University of Maryland, 1978 [5] Analysis And Comparative Study Of Searching Techniques, Ayush Pathak, International Journal Of Engineering Sciences and Research Technology (IJESRT), 2015 [6] Hybrid Search Algorithm, Asha Elza Jacob, Nikhil Ashodariya, Aakash Dhongade, International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS), 2017 [7] A Brief Study and Analysis Of Different Searching Algorithms, Najma Sultana, Smita Paira, Sourabh Chandra. Sk Safikul Alam, IEEE, 2017 [8] A Randomized Searching Algorithm and its Performance analysis with Binary Search and Linear Search Algorithms, Pranesh Das, Prof. Pabitra Mohan Khilar, The International Journal of Computer Science and Applications (TIJCSA), 2012 [9] Comparison Searching Process of Linear, Binary and Interpolation Algorithm, Robbi Rahim, Saiful Nurarif, Mukhlis Ramadhan, Siti Aisyah, Windania Purba, International Conference on Information and Communication Technology (IconICT) , 2017
References [1] Survey and Analysis of Searching Algorithms, Tahira Mahboob, Fatima Akhtar, Moquaddus Asif, Nitasha Siddique, Bushra Sikandar, International Journal of Computer Science Issues (IJCSI), 2015 [2] Comparative Analysis on Sorting and Searching Algorithms, B Subbarayudu, L Lalitha Gayatri, P Sai Nidhi, P. Ramesh, R Gangadhar Reddy, Kishor Kumar Reddy C, International Journal of Civil Engineering and Technology (IJCIET), 2017 [3] A Comparative Study of Sorting and Searching Algorithms, Ms Roopa K, Ms Reshma J. International Research Journal of Engineering and Technology (IRJET), 2018
© 2020, IRJET
|
Impact Factor value: 7.34
|
ISO 9001:2008 Certified Journal
|
Page 1584