In an unsorted array if we must search for a key then there is no other method apart from linear search. Linear searches the name suggests searches the entire array comparing each element with the key. this essentially requires searching the entire array in the worst case hence this is a O(n) approach.
If the array is sorted then we can do binary search in the array. In each step of the binary search we take the middle value and compare the middle value with the key. If the key is lesser than the middle element then we continue the search in the left half otherwise we search the right half. In each step we eliminate half of the remaining array. Thus this is how we do binary search on the array.
But if we must insert an element in this sorted array then we have to shift the entire array and insert the element at its proper position.
Thus, inserting an element in this array is O(n)
Binary tree can be used for this purpose. Binary tree reduces this time to O(logn) and also maintains the searching time to O(logn) only.
In a linked list to search for a particular element we have to linearly travel all the nodes comparing every node with the key and then returning the result. This is a O(n) approach.
There is no method of doing binary search in the linked list without the use of binary tree.
Thus binary tree can be used to convert linked list to list that makes binary search possible.
Linked list structure to support binary searching
We can use the above linked list structure to support binary searching in the linked list.
Instead of a single child of a node in the linked list here the linked list will contain two pointers one to its left child and the other one to its right child. In addition to these pointers each linked list contains information stored in its data field.
Thus using the above description we can design the structure of linked list as
Struct Node {
Struct node *leftChild, *rightChild;
Int data;
}
The head element of this structure is pointed to by a root element.
The root of this linked list contains the median of the dataset.
As shown, all the elements smaller than this element are on its left side and all the elements greater than this element are on the right side.
This property is followed at every node. The left subtree has elements which are lesser than the data of the node and the right subtree contains data values greater than the data of that node.
Pseudo code for this:
For searching an element in this structure:
struct node* search(int data){
struct node *current = root;
printf(“Visiting elements: “);
while(current->data != data){
if(current != NULL) {
printf(“%d “,current->data);
//go to left tree
if(current->data > data){ current = current->leftChild;
}//else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
}
}
return current;
}
For inserting an element in this structure
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
