Program in C & C++ to implement binary search method on Linked list

Program in C & C++ to implements binary search method on Linked list

C Program

#include<stdio.h>
#include<stdlib.h>
     struct Node {
         int data;
         struct Node *next;
     };
    typedef struct Node Node;
    Node *head = NULL, *tail = NULL;
    void insert(int data){
        Node *newN;
        newN = (Node*)malloc(sizeof(Node));
        newN->data = data;
        newN->next = NULL;
        if(head == NULL){
            head = tail = newN;
        }
        else{
           tail->next = newN;
            tail = newN;
        }
    } 
    void show(){
        Node *temp;
        if(head == 0){
           printf("List is empty.\n");
        }
        else{
            temp = head;
            while(temp != 0){
                printf("%4d",temp->data);
                temp = temp->next;
            }
        }
     }
    int length(){
        Node *temp;
        int count = 0;
        temp = head;
        while(temp != 0){
            count++;
            temp = temp->next;
        }
    return count; 
    }
    int valueAt(int pos){
        Node *temp;
        int count = 1;
        if(pos < 1 || pos > length()){
             printf("\nInvalid postion");
        }
        temp = head;
        while(count != pos){
            count++;
            temp = temp->next;
        }
        return temp->data;
    }
    void sort(){
        Node *temp, *i, *j;
        int temp1;
        for(temp = head, i = temp; i != 0; i = i->next)
          {
            for(j = i->next; j != 0; j = j->next){
                if(i->data > j->data){
                    temp1 = i->data;
                    i->data = j->data;
                    j->data = temp1;
                }
            }
        }
     }
    void binarySearch(int data){
        Node *temp;
        sort();
        int low = 1, high = length();
        int mid = 0;
        while(low <= high){
            mid = (low + high) / 2;
            if(valueAt(mid) == data){
                printf("\n  %d is found\n",data);
                return;
            }
            else if( data < valueAt(mid) ){
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }               
        }
        printf("\n %d is not fount.\n",data);
    }
    int main(){
      Node l1;
      insert(19);
      insert(56);
      insert(13);
      insert(78);
      insert(96);
      insert(48);
      insert(85);
      insert(76);
      insert(74);
      insert(35);
      printf("Elements of Linked list is ");
      show();
      binarySearch(23);
    return 0;
 }

C++ Program

    #include<iostream>
 using namespace std;
 class List {
     struct Node {
         int data;
         Node *next;
         Node(){
             data = 0;
             next = 0;
          }
          Node(int data){
              (*this).data = data;
              next = 0;
          }
          ~Node(){  delete next; }
     };
    Node *head = NULL, *tail = NULL;
    public:
       List(){

       }
       ~List(){
           delete head, tail;
       }
       void insert(int data){
            Node *newN;
            newN = new Node(data);
            if(head == NULL){
                head = tail = newN;
            }
            else{
                tail->next = newN;
                tail = newN;
            }
       } 
       void show(){
           Node *temp;
           if(head == 0){
               cout<<"List is empty.\n";
           }
           else{
               temp = head;
               while(temp != 0){
                   cout<<"  "<<temp->data;
                   temp = temp->next;
               }
           }
       }
       int length(){
           Node *temp;
           int count = 0;
           temp = head;
           while(temp != 0){
              count++;
              temp = temp->next;
           }
           return count;
       }
       int valueAt(int pos){
           Node *temp;
           int count = 1;
           if(pos < 1 || pos > length()){
               cout<<endl<<endl<<"Invalid postion";
           }
           temp = head;
           while(count != pos){
              count++;
              temp = temp->next;
           }
           return temp->data;
       }
       void binarySearch(int data){
           Node *temp;
           sort(); // sort function is use to sort List. We know the binary search method is always perform on sorted array, linked list etc.
           int low = 1, high = length();
           int mid = 0;
           while(low <= high){
               mid = (low + high) / 2;
               if(valueAt(mid) == data){  //Here valueAt(int pos) function return the value at given position
                   cout<<endl<<data<<" is found\n";
                   return;
               }
               else if( data < valueAt(mid) ){
                   high = mid - 1;
               }
               else {
                   low = mid + 1;
               }               
           }
           cout<<endl<<data<<" is not fount.\n";
       }
     void sort(){
         Node *temp, *i, *j;
         int temp1;
         for(temp = head, i = temp; i != 0; i = i->next)
          {
              for(j = i->next; j != 0; j = j->next){
                  if(i->data > j->data){
                      temp1 = i->data;
                      i->data = j->data;
                      j->data = temp1;
                  }
              }
          }
     }
 };
 int main(){
    List l1;
    l1.insert(68);
    l1.insert(12);
    l1.insert(28);
    l1.insert(23);
    l1.insert(74);
    l1.insert(54);
    cout<<"Elements of Linked list is ";
    l1.show();
    l1.binarySearch(23); // Call binarySearch function 
    return 0;
 }

Output :-

Related Programs         1. Program in C to implement singly linked list insert data and display data.

          2.  Program in C to display data of singly linked list in reverse order using recursive function.