Binary Search In Linked List
Kumar Sanu
Kumar Sanu,*Department of Computer Science, Chandigarh University, Chandigarh, India.
Manuscript received on September 21, 2019. | Revised Manuscript received on October 05, 2019. | Manuscript published on October 30, 2019. | PP: 3151-3153 | Volume-9 Issue-1, October 2019 | Retrieval Number: A9775109119/2019©BEIESP | DOI: 10.35940/ijeat.A9775.109119
Open Access | Ethics and Policies | Cite | Mendeley
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: 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.
Keywords: Array of pointers, Binary Search, Indexing, Linked List.