Open AccessBinary Search In Linked List
Author(s) -
Kumar Sanu*
Publication year - 2019
Publication title -
international journal of recent technology and engineering
Language(s) - English
Resource type - Journals
ISSN - 2277-3878
DOI - 10.35940/ijrte.d7296.118419
Subject(s) - binary search algorithm , binary number , binary search tree , computer science , self balancing binary search tree , ternary search tree , search engine indexing , optimal binary search tree , search algorithm , linear search , traverse , element (criminal law) , time complexity , mathematics , algorithm , binary tree , information retrieval , search tree , arithmetic , geodesy , 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