Binary Search on Singly Linked ListGiven a singly linked list and a key, find key using binary search approach. Show
In main function, function InsertAtHead inserts value at the beginning of linked list. Inserting such values(for sake of simplicity) so that the list created is sorted. C++
Java
Python
C#
Javascript
Output:
Present
Time Complexity: O(N)
Article Tags :
Divide and Conquer Linked List Searching
Binary Search Practice Tags :
Linked List Searching Divide and Conquer Binary Search Explanation of using Binary SearchTo perform a Binary Search Algorithm on Singly Linked Lists, determination of the middle element is important. Binary Search is fast and efficient because accessing the middle elemen is fast. In arrays, binary search takes O(1) time to access middle element. But memory allocation for the singly linked list is non-contiguous, which makes finding the middle element difficult and time consuming. The node structure for Linked List is as follows: // Node structure struct Node { int data; Node* next; };Finding middle element: Two pointer approach
Code// function to find out middle element Node* middle(Node* start, Node* last) { // if start points to NULL and is empty if (start == NULL) return NULL; Node* slow = start; Node* fast = start -> next; while (fast != last) { // fast is moved one step ahead fast = fast -> next; // if fast is not the last element if (fast != last) { // slow pointer is moved one step ahead slow = slow -> next; // fast pointer is moved second step ahead fast = fast -> next; } } return slow; }Binary Search on Singly Linked List in C++C++Server Side ProgrammingProgramming A singly linked list is a linked list (a data structure that stores a node’s value and the memory location of the next node) which can go only one way. A binary search is a search algorithm based on divide and rule. That finds the middle element of the structure and compares and uses recursive calls to the same algorithm for inequality. Here, we are given a singly linked list and an element to be found using a binary search. Since the singly linked list is a data structure that uses only one pointer, it is not easy to find its middle element. To mid of singly linked list, we use two pointer approaches. |