Binary Search in Cpp

 

#include <iostream>

using namespace std;

int main()

{

    int a[5], i, num;

    int low, high, mid;

• //num – Number that we want to search.

• //low – Starting position of the array.

• //high – Last position of the array.

• //mid – Middle position of the array.

    cout << "Enter 5 numbers in ascending order: ";

    for(i = 0; i < 5; i++)

    {

        cin >> a[i];

    }

    cout << "Enter number to search: ";

    cin >> num;

    low = 0;//low = 0 means the first position of the array.

    high = 4; //high = 4 means the last position of the array.

    while(low <= high)

    {

        mid = (low + high) / 2;  

//Finds the middle position of the array.

//For example, (0 + 4) / 2 = 2.

//So, the middle position is 2 (number 30).

        if(a[mid] == num)

        {

            cout << "Number found";

            return 0;

        }

        if(num > a[mid])

        {

            low = mid + 1;  //If the searching number is greater than the middle number, search the right side.

mid + 1 moves the starting position to the right side.

        }

        else

        {

            high = mid - 1;//If the searching number is smaller than the middle number, search the left side. mid - 1 moves the ending position to the left side.

        }

    }

    cout << "Number not found";

    return 0;

}

Read More

Linear Search in Cpp

 #include <iostream>

using namespace std;

int main()

{

    int a[5], i, search;

    cout << "Enter 5 numbers: ";

    for(i = 0; i < 5; i++)

    {

        cin >> a[i];

    }

    cout << "Enter number to search: ";

    cin >> search;

    for(i = 0; i < 5; i++)

    {

        if(a[i] == search)

        {

            cout << "Number found at position " << i + 1;

            return 0;

        }

    }

    cout << "Number not found";

    return 0;

}

Read More

Insertion Sort in Cpp

#include <iostream>

using namespace std;

int main()

{

    int a[5], i, j, temp;

    cout << "Enter 5 numbers: ";

    for(i = 0; i < 5; i++)

    {

        cin >> a[i];

    }

    for(i = 1; i < 5; i++)//Starts comparing from the second element. 

    {

        for(j = i; j > 0; j--)//- Compares the current element with the previous element. 

        {

            if(a[j] < a[j-1])- //Checks whether the current number is smaller than the previous number. 

            {

                temp = a[j];  //Swaps the two numbers. 

                a[j] = a[j-1];

                a[j-1] = temp;

            }

        }

    }

    cout << "Sorted array: ";

    for(i = 0; i < 5; i++)

    {

        cout << a[i] << " ";

    }

    return 0;

}

Read More

Write a Program PreOrder, PostOrder, InOrder Traversal

#include <iostream>

using namespace std;

struct Node

{

    int data;

    Node *left;

    Node *right;

};

// Create a new node

Node* createNode(int value)

{

    Node *newNode = new Node;

    newNode->data = value;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

// Preorder Traversal (Root, Left, Right)

void preorder(Node *root)

{

    if (root != NULL)

    {

        cout << root->data << " ";

        preorder(root->left);

        preorder(root->right);

    }

}

// Inorder Traversal (Left, Root, Right)

void inorder(Node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        cout << root->data << " ";

        inorder(root->right);

    }

}

// Postorder Traversal (Left, Right, Root)

void postorder(Node *root)

{

    if (root != NULL)

    {

        postorder(root->left);

        postorder(root->right);

        cout << root->data << " ";

    }

}

int main()

{

    // Create a tree

    Node *root = createNode(10);

    root->left = createNode(20);

    root->right = createNode(30);

    root->left->left = createNode(40);

    root->left->right = createNode(50);

    root->right->left = createNode(60);

    root->right->right = createNode(70);

    cout << "\nPreorder Traversal: ";

    preorder(root);

    cout << "\nInorder Traversal: ";

    inorder(root);

    cout << "\nPostorder Traversal: ";

    postorder(root);

    return 0;

}

Read More

Write a Program Implementation of a BST ,Add,Search ,Min,Max

 

#include <iostream>

using namespace std;

struct Node

{

    int data;

    Node *left;

    Node *right;

};

// Create a new node

Node* createNode(int value)

{

    Node *newNode = new Node;

    newNode->data = value;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

// Insert a node

Node* insert(Node *root, int value)

{

    if (root == NULL)

        return createNode(value);

    if (value < root->data)

        root->left = insert(root->left, value);

    else if (value > root->data)

        root->right = insert(root->right, value);

    return root;

}

// Search an element

void search(Node *root, int key)

{

    if (root == NULL)

    {

        cout << "Element not found";

        return;

    }

    if (root->data == key)

    {

        cout << "Element found";

    }

    else if (key < root->data)

    {

        search(root->left, key);

    }

    else

    {

        search(root->right, key);

    }

}

// Find minimum value

int findMin(Node *root)

{

    while (root->left != NULL)

    {

        root = root->left;

    }

    return root->data;

}

// Find maximum value

int findMax(Node *root)

{

    while (root->right != NULL)

    {

        root = root->right;

    }

    return root->data;

}

// Display BST using Inorder

void inorder(Node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        cout << root->data << " ";

        inorder(root->right);

    }

}

int main()

{

    Node *root = NULL;

    int choice, value;

    do

    {

        cout << "\n\n--- BINARY SEARCH TREE ---";

        cout << "\n1. Insert";

        cout << "\n2. Search";

        cout << "\n3. Minimum";

        cout << "\n4. Maximum";

        cout << "\n5. Display";

        cout << "\n6. Exit";

        cout << "\nEnter your choice: ";

        cin >> choice;

        switch (choice)

        {

            case 1:

                cout << "Enter value: ";

                cin >> value;

                root = insert(root, value);

                cout << "Node inserted";

                break;

            case 2:

                cout << "Enter value to search: ";

                cin >> value;

                search(root, value);

                break;

            case 3:

                if (root == NULL)

                    cout << "Tree is empty";

                else

                    cout << "Minimum value = " << findMin(root);

                break;

            case 4:

                if (root == NULL)

                    cout << "Tree is empty";

                else

                    cout << "Maximum value = " << findMax(root);

                break;

            case 5:

                cout << "BST Elements: ";

                inorder(root);

                break;

            case 6:

                cout << "Program ended";

                break;

            default:

                cout << "Invalid choice";

        }

    } while (choice != 6);

    return 0;

}

Read More