// C++  Binary Search
#include <iostream>
using namespace std;

int binarySearch(int arr[], int start, int end, int x)
{
    while (start <= end) {
        int m = start + (end - start) / 2;

        // Check if x is present at mid
        if (arr[m] == x)
            return m;

        // If x greater, ignore left half
        if (arr[m] < x)
            start = m + 1;

        // If x is smaller, ignore right half
        else
            end = m - 1;
    }
    return -1;
}

int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 40;
    int end = 5;

    int result = binarySearch(arr, 0, end - 1, x);

    if(result == -1)
        cout << "Element is not present in array";
    else
        cout << "Element is present at index " << result;
    return 0;
}