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

#define ARRAY_SIZE 16  // Size of the array
#define NUM_THREADS 4  // Number of threads
#define TARGET 7       // Number to search for

int array[ARRAY_SIZE];
int found = -1;  // Index of the found element (-1 if not found)

// Struct for passing data to threads
typedef struct {
    int low;
    int high;
} SearchRange;

// Function executed by the thread
void *binary_search_thread(void *arg) {
    SearchRange *range = (SearchRange *)arg;
    int low = range->low;
    int high = range->high;
    int mid;

    while (low <= high && found == -1) {
        mid = low + (high - low) / 2;
        if (array[mid] == TARGET) {
            found = mid;  // Set the found index
            break;
        } else if (array[mid] < TARGET) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    pthread_exit(NULL);
}

int main() {
    pthread_t threads[NUM_THREADS];
    SearchRange ranges[NUM_THREADS];
    int segment_size = ARRAY_SIZE / NUM_THREADS;

    // Initialize and sort the array
    for (int i = 0; i < ARRAY_SIZE; i++) {
        array[i] = i;  // Fill the array with sorted numbers
    }

    // Creating threads for binary search
    for (int i = 0; i < NUM_THREADS; i++) {
        ranges[i].low = i * segment_size;
        ranges[i].high = (i + 1) * segment_size - 1;
        pthread_create(&threads[i], NULL, binary_search_thread, &ranges[i]);
    }

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

    // Check if the target was found
    if (found != -1) {
        printf("Target found at index: %d\n", found);
    } else {
        printf("Target not found\n");
    }

    return 0;
}