Research Paper
Computer Science
E-ISSN No : 2454-9916 | Volume : 3 | Issue : 1 | Jan 2017
DESIGNING AND IMPLEMENTING DATA STRUCTURE WITH SEARCH ALGORITHM TO SEARCH ANY ELEMENT FROM A GIVEN LIST HAVING CONSTANT TIME COMPLEXITY 1
Dr. Vimal P. Parmar | Dr. CK Kumbharana 1 2
2
Research Scholar, Department of Computer Science, Saurashtra University Rajkot. Gujarat, India. Head Guide, Department of Computer Science, Saurashtra University Rajkot, Gujarat, India.
ABSTRACT Search process is fundamental in computer science. To search an element various data structure are developed and implemented. Searching a word from a dictionary requires alphabetical arrangement of the words for fast searching. To search a record from a database an SQL query with WHERE clause is useful. To search specific information from internet, search engine is widely used. Searching is weaved centrally in almost all computer applications. This research paper is designed with available different search techniques and its time complexity. Various data structures are available with specific application needs. Linear search, binary search, binary search tree, hashing techniques and many other search techniques are studied and then prepared a hybrid data structure involving linked list with an array to directly locate an element. The process actually does not involve any searching technique to search element by comparison but using indexed organization of data structure makes it possible to determine whether an element exists in a list or not. The model is designed to prepare a data structure suitable for fast searching. Direct search can also be implemented using hashing techniques involving some mathematical computation to search any element in a constant time. Similarly, here is an effort is being made to search any element from a given list with constant time involving no mathematical computation to search a key like hashing technique. At last paper is concluded with limitations and future enhancement of the proposed technique. KEYWORDS: Searching, Indexing, Linear Search, Binary Search, Binary Search Tree, Hashing Technique, Time Complexity, Space Complexity. I. INTRODUCTION Most of the computer applications involve searching. Searching an element from a list or a record from a database requires comparison. Hashing technique is a one that search an element directly by mapping a search key to an index position. Mapping is performed based on some mathematical calculation which can be implemented using any hash function. The main advantage of hashing is the time required to search any element is constant and is proportional to the time required by hashing function. Linear search technique requires scanning and comparing one by one element of a list with a search key. So the time required by linear search is proportional to the total number of elements in a list. If an element to be searched is located nearer to first element it requires less time as opposed to an element which is located at the end of the list or an element does not exist at all in the list requires maximum time because it requires maximum comparisons. The solution to this is the binary search which divides the search space half at each comparison giving fast performance compared to the linear search. Binary search tree is construction of a tree and traversing it left or right branch based on the condition. The performance is similar to that of binary search. Binary search requires elements to be arranged in some order to implement it. Here is an effort is being made to search an element in a constant time with no mathematical calculation by directly locating the search element if exists. To implement the search algorithm efficiently, a data structure is designed involving linked list, array and pointer. Entire searching process is implemented in C language and tested with sample data. At last paper is concluded with limitations and future enhancement to the proposed process. Time complexity is the time required by any algorithm where as space complexity is the amount of memory required to store data used by algorithm. Asymptotic notation Big O is used to analyze the algorithm by determining the key operations of the algorithm. Here proposed search process is compared and analyzed with existing searching algorithm using Big O notation. II. LINEAR SEARCH ALGORITHM Linear search algorithm searches an element by comparing the given key element to be searched with all the elements of the given list starting from first element. Following algorithm is a sequential or linear search algorithm. ALGORITHM LINEAR_SEARCH (Vector V, Integer N, Integer X) : Given a vector V consisting of N elements and an element X to be searched from a vector V. Table 1 : Linear Search Algorithm 1. [Search for the location of value X in vector V] I=1 Repeat WHILE I <= N IF V[I] = X THEN WRITE ('ELEMENT FOUND') RETURN (I) ELSE I=I+1 2. WRITE ('ELEMENT NOT FOUND') RETURN (0)
Above algorithm starts searching for a given value of X from first position of the vector. It compares the first element V[1] with X and if match is found it prints the message of found and returns the position where X is located in vector V otherwise increments value of I from 1 to 2 to compare next element. This process continues for N times and once match is found it returns the value of location I in vector V. If not match found after comparing all the elements in a vector V it prints the message of not found and returns index 0 indicating element X is not found in vector V. The time required by linear search is proportional to total elements N in a vector V as key operation in this algorithm is comparison operation IF V[I] = X. So the time complexity for linear search is O(N). The best case is one where less comparisons is required that is element is located at first position and time required for this case is constant regardless of number of elements N which is denoted as O(1). The worst case is the case in which search element is located at Nth position which requires N comparison or an element does not exist in vector which also requires N comparisons. Generally algorithm analysis is performed by considering the worst case so here the time complexity for search process is O (N). Third case is the average case analysis as we don't know where the element is actually located so in average case using probability linear search requires O (N/2) time. But again it is proportional to N and asymptotic analysis of time ignores lower order terms and constants and considers only the higher order terms so it is proportional to N. So the linear search performs on time complexity of O (N). That means the time required by algorithm is based on the total elements in a vector. This is the simplest search process. To improve the performance other solution is required. Widely used search process is the binary search that dramatically reduces the time compared to with that of linear search. III. BINARY SEARCH ALGORITHM Binary search algorithm requires all the elements in a vector in ascending or descending order. It first searches the vector with its center element by comparing it with a given value. If match is found algorithm terminates by returning its position and if no match is found it reduces the search space to the half of the original size. If search element is less than the middle element then only first half of the vector is searched and in case if it is greater than the middle element then only second half of the vector is searched in next iteration. In either of the case the list to be searched is reduced to half at each iteration of the search process. Following lists the binary search algorithm. ALGORITHM BINARY_SEARCH (Vector V, Integer N, Integer X) : Given a vector V consisting of N ordered elements arranged in ascending order and an element X to be searched from a vector V. The variables LOW, HIGH and MID denote the lower, higher and middle limits of search interval. This function returns the index of the vector element if the search is successful otherwise returns 0.
CopyrightŠ 2016, IERJ. This open-access article is published under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License which permits Share (copy and redistribute the material in any medium or format) and Adapt (remix, transform, and build upon the material) under the Attribution-NonCommercial terms.
International Education & Research Journal [IERJ]
109