#include <iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>

struct Num
{
    int n;
    struct Num *next;
};
Num *Start = NULL;
Num *Rear = NULL;

void Insert()
{
    Num *ptr = new Num;
    cout << "Enter number: ";
    cin >> ptr->n;
    ptr->next = NULL;
    if (Start == NULL)
        Start = Rear = ptr;
    else
    {
        Rear->next = ptr;
        Rear = ptr;
    }
}

Num *midElement(Num *s, Num *r)
{
    int count = 0;
    Num *temp = new Num;
    temp = s;
    while (temp != r)
    {
        count++;
        temp = temp->next;
    }
    int i = 0;
    temp = s;
    while (i < count / 2)
    {
        temp = temp->next;
        i++;
    }
    // cout<<"Mid= "<<temp->n<<"\n";
    return temp;
}

void BSearch()
{
    int item, flag = 0;
    cout << "Enter the number to search: ";
    cin >> item;
    Num *head = new Num;
    head = Start;
    Num *tail = new Num;
    tail = NULL;
    do
    {
        Num *mid = midElement(head, tail);
        if (mid == NULL)
        {
            cout << "Mid is empty";
            break;
        }

        if (mid->n == item)
        {
            flag++;
            break;
        }
        else if (mid->n < item)
        {
            head = mid->next;
            // cout<<"head= "<<head->n<<"\n";
        }
        else
        {
            tail = mid;
            // cout<<"Tail= "<<tail->n<<"\n";
        }
    } while ((head != tail) || tail == NULL);
    if (flag != 0)
        cout << "Item found";
    else
        cout << "Item NOT found";
}

int main()
{
    clrscr();
    cout << "Enter 10 ascending sorted values into the linked list:\n";
    for (int i = 0; i < 10; i++)
    {
        Insert();
    }
    BSearch();
    getch();
    return 0;
}

#include <iostream>
using namespace std;

struct Num
{
    int n;
    struct Num *next;
};
Num *Start = NULL;
Num *Rear = NULL;

void Insert()
{
    Num *ptr = new Num;
    cout << "Enter number: ";
    cin >> ptr->n;
    ptr->next = NULL;
    if (Start == NULL)
    {
        Start = Rear = ptr;
    }
    else
    {
        Rear->next = ptr;
        Rear = ptr;
    }
}

Num *midElement(Num *s, Num *r)
{
    int count = 0;
    Num *temp = new Num;
    temp = s;
    while (temp != r)
    {
        count++;
        temp = temp->next;
    }
    int i = 0;
    temp = s;
    while (i < count / 2)
    {
        temp = temp->next;
        i++;
    }
    // cout<<"Mid= "<<temp->n<<"\n";
    return temp;
}

void BSearch()
{
    int item, flag = 0;
    cout << "Enter the number to search: ";
    cin >> item;
    Num *head = new Num;
    head = Start;
    Num *tail = new Num;
    tail = NULL;
    do
    {
        Num *mid = midElement(head, tail);
        if (mid == NULL)
        {
            cout << "Mid is empty";
            break;
        }

        if (mid->n == item)
        {
            flag++;
            break;
        }
        else if (mid->n < item)
        {
            head = mid->next;
            // cout<<"head= "<<head->n<<"\n";
        }
        else
        {
            tail = mid;
            // cout<<"Tail= "<<tail->n<<"\n";
        }
    } while ((head != tail) || tail == NULL);
    if (flag != 0)
    {
        cout << "Item found";
    }
    else
    {
        cout << "Item NOT found";
    }
}

int main()
{
    cout << "Enter 10 ascending sorted values into the linked list:\n";
    for (int i = 0; i < 10; i++)
    {
        Insert();
    }
    BSearch();
    return 0;
}