using namespace std;
#include <iostream>
 
// linear search

int LinearSearch(int arr[], int size, int key)
{

    for (int i = 0; i < size; i++)
    {

        if (arr[i] == key)
        {
            key = arr[i];
            cout << "Element found at Index " << i << " ";
        }
    }
    return -1;
}

int BinarySearch(int arr[], int size, int key)
{
    // Array: {1, 2, 3, 4, 30, 56, 62, 63, 64, 70}
    // Key: 64
    // Size: 10

    int start = 0;      // Initialize start index to 0
    int end = size - 1; // Initialize end index to the last element

    // Loop continues as long as start is less than or equal to end
    while (start <= end)
    {
        // Calculate the middle index to avoid overflow
        int mid = start + (end - start) / 2; // mid is 9/2 = 4
        int mid_element = arr[mid];          // arr[4] is 30 which is the mid element

        // Check if the mid element is the key
        if (mid_element == key)
        {
            return mid; // If found, return the index of the mid element
        }

        // If mid element is less than the key
        if (mid_element < key)
        {
            // Key is in the right half
            start = mid + 1; // Move the start index to mid + 1
        }
        else
        {
            // Key is in the left half
            end = mid - 1; // Move the end index to mid - 1
        }
    }

    return -1; // If the key is not found, return -1
}

int main()
{

    int key = 64;
    int size = 10;
    int arr[] = {1, 2, 3, 4, 30, 56, 62, 63, 64, 70};
    LinearSearch(arr, size, key);

    int index = BinarySearch(arr, size, key);

    if (index != -1)
    {
        cout << "Element found at index " << index << endl;
    }
    else
    {
        cout << "Element not found" << endl;
    }
}