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

int step = 0;

int binary_search(int target, int left, int right, int arr[]) {
    step++;
    int mid = (left + right) / 2;

    if (target == arr[mid]) return mid;
    if (target < arr[mid])
        right = mid;
    if (target > arr[mid])
        left = mid;

    return binary_search(target, left, right, arr);
}

int main() {
    int arr[200];
    int bukkit[100] = {0};
    int i, j, t;

    // Random generate data
    for (i = 0; i < 200; i++)
        arr[i] = rand() % 100;

    // Display data
    printf("Before\n");
    for (i = 0; i < 20; i++) {
        printf("%d ", arr[i]);
        bukkit[arr[i]]++;
    }

    // Sort data by counting sort
    printf("\nAfter\n");
    for (t = i = 0; i < 100; i++)
        for (j = 0; j < bukkit[i]; j++) {
            printf("%d ", i);
            arr[t++] = i;
        }
    printf("\n");

    int idx = binary_search(86, 0, 20, arr);
    while (arr[idx-1] == arr[idx]) idx--;
    printf("arr[%d] = %d\n", idx, 2);
    printf("Cost: %d\n", step);
    return 0;
}