Note : The following solution assumes the structure of linked list to be as the one defined in : Structure of linked list
Performing a binary search on linked list is never a good idea , as usually its running time can exceed that of standard ( linear ) search.
The biggest reason why binary search is such a fast algorithm on arrays , but is quite slow for linked list is that :
In array accessing the middle index between two given array index is very easy and very fast . It usually involves finding out the average of the two indexes and accessing the element, thus the running time is constant .i.e O(1)
However in linked list , to access the middle node , we need to traverse the linked list , node by node ... thus the running time of finding middle node could be in order of O(n)
In practical life , if we need to implement a search on linked list , then we should always prefer linear search ...
However , here's an algorithm that performs binary search on linked list :
Firstly , the following solution will use a modified version of the algorithm to find out the middle node of a linked list .
In this version , rather than finding the middle node of the entire linked list , we find out the middle node between any two nodes of a linked list.
Code Snippet :
01
// function to find the middle node of the part of linked list starting with startNode and ending with endNode
02
// It uses the fast & slow pointer approach
03
04
node * middleNode( node * startNode , node * endNode)
05
{
06
if( startNode == NULL )
07
{
08
// Linked list is empty
09
return NULL;
10
}
11
12
node * slowPtr = startNode;
13
node * fastPtr = startNode -> next;
14
15
while ( fastPtr != endNode )
16
{
17
fastPtr = fastPtr -> next ;
18
19
if( fastPtr != endNode )
20
{
21
slowPtr = slowPtr -> next ; // Notice that for each loop iteration :
22
fastPtr = fastPtr -> next ; // slowPtr moves just one location
23
// while fastPtr moves two nodes at a time.
24
}
25
}
26
27
return slowPtr ; // At the end , the slowPtr will be pointing to the middle node
28
}
Now once we have the function to get middle node in place , we now need to focus on the algorithm itself ..
We proceed in manner similar to binary search in arrays , we have a starting node ( set to Head ) , an ending node ( set to NULL )
We then find out the middle node between the startNode & endNode
If middleNode matches the required value to search , we have found the reqd node and we return it
else , if middleNode's data < value , then we need to move to upper half ( by setting startNode to middle's next )
else we move to lower half ( by setting endNode to middle )
Now the above algorithm seems simple enough ... however there is a big catch .. When do we terminate the loop ??
While dealing with arrays , we would have terminated if index of start > index of end ...
However here we are dealing with nodes .. and there is no concept of index ...
We could then keep a check on values .. and terminate if : start's data > end's data ... However even this check would have failed has the list comprised of all nodes with equal value...
After some observation .. one can see .. that when the entire array gets scanned ... we then have the situation ... where endNode points directly before startNode ... i.e. endNode->next == startNode !!!!!
Now once we have the following logic clear ... we can formulate the function that performs the above logic :
Code Snippet :
01
node * binarySearch( int valueToSearch )
02
{
03
node * startNode = head;
04
node * endNode = NULL;
05
06
do
07
{
08
node * middle = middleNode( startNode , endNode );
09
10
if( middle == NULL )
11
{
12
// element not present
13
return NULL;
14
}
15
16
if( middle->data == valueToSearch )
17
{
18
return middle;
19
}
20
else if ( middle->data < valueToSearch )
21
{
22
// need to search in upper half
23
startNode = middle->next;
24
}
25
else
26
{
27
// need to search in lower half
28
endNode = middle;
29
}
30
31
}while( endNode == NULL || endNode->next != startNode );
32
33
// data not present
34
return NULL;
35
}
