#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define NUM_THREADS 4 // Number of threads to use
#define ARRAY_SIZE 1000000 // Size of the sorted array

// Shared data structure to hold thread arguments
struct ThreadArgs {
    int* arr;
    int target;
    int start;
    int end;
    int result;
};

// Function to perform binary search on a sorted array
void* binarySearch(void* arg) {
    struct ThreadArgs* threadArgs = (struct ThreadArgs*)arg;
    int* arr = threadArgs->arr;
    int target = threadArgs->target;
    int start = threadArgs->start;
    int end = threadArgs->end;

    while (start <= end) {
        int mid = start + (end - start) / 2;

        if (arr[mid] == target) {
            threadArgs->result = mid;
            return NULL;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    // If the target is not found, set the result to -1
    threadArgs->result = -1;
    return NULL;
}

int main() {
    static int arr[ARRAY_SIZE] = {};
    for (int i = 0; i < ARRAY_SIZE; i++) arr[i] = i * 2;
    int target = 233333;

    // Initialize the threads and their arguments
    pthread_t threads[NUM_THREADS];
    struct ThreadArgs threadArgs[NUM_THREADS];

    int step = ARRAY_SIZE / NUM_THREADS;
    int remaining = ARRAY_SIZE % NUM_THREADS;
    int start = 0;

    // Create threads and assign the binary search tasks
    for (int i = 0; i < NUM_THREADS; i++) {
        int end = start + step - 1;
        if (i < remaining) {
            end++;
        }

        threadArgs[i].arr = arr;
        threadArgs[i].target = target;
        threadArgs[i].start = start;
        threadArgs[i].end = end;

        pthread_create(&threads[i], NULL, binarySearch, (void*)&threadArgs[i]);

        start = end + 1;
    }

    // Wait for all threads to finish
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    // Find the first thread that has found the target
    int result = -1;
    for (int i = 0; i < NUM_THREADS; i++) {
        if (threadArgs[i].result != -1) {
            result = threadArgs[i].result;
            break;
        }
    }

    if (result != -1) {
        printf("Target %d found at index %d.\n", target, result);
    } else {
        printf("Target %d not found in the array.\n", target);
    }

    return 0;
}