Advertisement
kazol196295

binary search in linked list

May 18th, 2022
696
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define lli long long int
  3. #define el  endl
  4. #define oo  cout
  5. #define ii  cin
  6. #define FOR(i,a,b,c) for (int i = (a); i < (b); i=i+(c))
  7.  
  8.  
  9. using namespace std;
  10.  
  11. class node{
  12.     public:
  13. lli   value;
  14. node *next;
  15.  
  16. node(lli v){
  17. value=v;
  18. next=NULL;
  19.  
  20. }};
  21.  
  22. node *head=NULL,*tail=NULL,*tem;
  23.  
  24. void insert_at_back(lli v){
  25.  
  26. node *p=new node(v);
  27.  
  28. if(head==NULL){
  29.     head=p;
  30.     tail=p;
  31.     return;
  32. }
  33.  
  34. tem=head;
  35. while(tem->next!=NULL){
  36.     tem=tem->next;
  37. }
  38.  
  39. tem->next=p;
  40. tail=p;
  41.  
  42. }
  43.  
  44.  
  45. void display(){
  46.  
  47. tem=head;
  48. while(tem!=NULL){
  49.  
  50.     oo<<tem->value<<" ";
  51.     tem=tem->next;
  52. }
  53. oo<<el;
  54.  
  55. }
  56.  
  57. node *middle(node *f,node *l){
  58.  
  59.  
  60. node *mid=f;
  61.  
  62. while(f!=l){
  63.     f=f->next;
  64.     if(f!=l){
  65.         f=f->next;
  66.         mid=mid->next;
  67.     }
  68. }
  69.  
  70. return mid;
  71.  
  72. }
  73.  
  74.  
  75. void Binary_Search(){
  76. oo<<"Search Item:";
  77. lli x;
  78. ii>>x;
  79.  
  80. node *first=head;
  81. node *last=tail;
  82. node *mid=middle(first,last);
  83.  
  84. while(first!=last){
  85.  
  86.     if(mid->value == x){
  87.         oo<<x<<" is Found !"<<el;
  88.         return;
  89.     }
  90.     else if(mid->value > x){
  91.         last=mid;
  92.         mid=middle(first,last);
  93.     }
  94.     else if(mid->value < x){
  95.         first=mid->next;
  96.         mid=middle(first,last);
  97.     }
  98.  
  99. }
  100.  
  101. oo<<x<<" Not Found!"<<el;
  102.  
  103. }
  104.  
  105. int main()
  106. {
  107. lli n,v;
  108. oo<<"Number: ";
  109. ii>>n;
  110.  
  111. oo<<"Numbers: ";
  112. FOR(i,0,n,1){
  113. ii>>v;
  114. insert_at_back(v);
  115. }
  116. display();
  117.  
  118. Binary_Search();
  119.  
  120. return 0;
  121. }
Advertisement
RAW Paste Data Copied
Advertisement