Binary Search In Linked List
Kumar Sanu
Kumar Sanu, Research Scholar, Department of Computer Science Engineering, Chandigarh University, Ajitgarh (Punjab) India.
Manuscript received on November 22, 2019. | Revised Manuscript received on November 28, 2019. | Manuscript published on November 30, 2019. | PP: 2684-2686 | Volume-8 Issue-4, November 2019. | Retrieval Number: D7296118419/2019©BEIESP | DOI: 10.35940/ijrte.D7296.118419
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© 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.
Scope of the Article: Search-Based Software Engineering.