Open AccessBinary Search In Linked List
Author(s) -
Kumar Sanu*
Publication year - 2019
Publication title -
international journal of engineering and advanced technology
Language(s) - English
Resource type - Journals
ISSN - 2249-8958
DOI - 10.35940/ijeat.a9775.109119
Subject(s) - binary search algorithm , binary number , binary search tree , computer science , ternary search tree , self balancing binary search tree , search engine indexing , optimal binary search tree , linear search , traverse , search algorithm , element (criminal law) , time complexity , node (physics) , theoretical computer science , algorithm , mathematics , binary tree , information retrieval , search tree , arithmetic , geodesy , structural engineering , engineering , political science , law , interval tree , geography
This paper is based on an approach to implement Binary Search in Linked List. Binary Search is divide and conquer approach to search an element from the list of sorted element. In Linked List we can do binary search but it has time complexity O(n) that is same as what we have for linear search which makes Binary Search inefficient to use in Linked List. The main problem that binary search takes O(n) time in Linked List due to fact that in linked list we are not able to do indexing which led traversing of each element in Linked list take O(n) time.In this paper a method is implemented through which binary search can be done with time complexity of O(log2n). This is done with the help of auxiliary array. Auxiliary array helps in indexing of linked list through which one can traverse a node in O(1) complexity hence reducing the complexity of binary search to O(log2n) hence increasing efficiency of binary search in linked List.