#include <iostream>
using namespace std;

// Binary search function: returns the index of target or -1 if not found
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // Check if target is at mid
        if (arr[mid] == target) {
            return mid;
        }
        // If target is smaller, ignore right half
        else if (target < arr[mid]) {
            right = mid - 1;
        }
        // If target is larger, ignore left half
        else {
            left = mid + 1;
        }
    }

    // Element not found
    return -1;
}

int main() {
    // Sorted array (required for binary search)
    int arr[] = {3, 8, 15, 20, 28, 35, 50};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 28;

    int index = binarySearch(arr, size, target);

    if (index != -1) {
        cout << "Target " << target << " found at index " << index << endl;
    } else {
        cout << "Target " << target << " not found in the array." << endl;
    }

    return 0;
}